{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Max Submatrix LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getMaxMatrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大子矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个正整数、负整数和 0 组成的 N &times; M&nbsp;矩阵，编写代码找出元素总和最大的子矩阵。</p>\n",
    "\n",
    "<p>返回一个数组 <code>[r1, c1, r2, c2]</code>，其中 <code>r1</code>, <code>c1</code> 分别代表子矩阵左上角的行号和列号，<code>r2</code>, <code>c2</code> 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。</p>\n",
    "\n",
    "<p><strong>注意：</strong>本题相对书上原题稍作改动</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre><strong>输入：\n",
    "</strong><code>[\n",
    "&nbsp;  [-1,<strong>0</strong>],\n",
    "&nbsp;  [0,-1]\n",
    "]</code>\n",
    "<strong>输出：</strong>[0,1,0,1]\n",
    "<strong>解释：</strong>输入中标粗的元素即为输出所表示的矩阵</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>说明：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= matrix.length, matrix[0].length &lt;= 200</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [max-submatrix-lcci](https://leetcode.cn/problems/max-submatrix-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [max-submatrix-lcci](https://leetcode.cn/problems/max-submatrix-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[9,-8,1,3,-2],[-3,7,6,-2,4],[6,-4,-4,8,-7]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "     \n",
    "\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        dim1, dim2 = len(matrix), len(matrix[0])\n",
    "        tl1,tl2,br1,br2=0,0,0,0\n",
    "        ma=matrix[0][0]\n",
    "        for top in range(dim1):\n",
    "            sumli=[0]*dim2\n",
    "            for bot in range(top, dim1):\n",
    "                pre=0\n",
    "                s=0\n",
    "                for k in range(0, dim2):\n",
    "                    sumli[k]+=matrix[bot][k]\n",
    "                    pre+=sumli[k]\n",
    "                    if(pre>ma):\n",
    "                        ma=pre\n",
    "                        tl1,tl2,br1,br2=top,s,bot,k\n",
    "                    if(pre<0):\n",
    "                         pre=0\n",
    "                         s=k+1\n",
    "        return tl1,tl2,br1,br2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# ### 前缀和 42/45--pass\n",
    "# class Solution:\n",
    "#     def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "#         res=[]\n",
    "#         ans=0\n",
    "#         m,n=len(matrix),len(matrix[0])\n",
    "#         ss=[[0]*n for _ in range(m)]\n",
    "#         for i in range(m): ### 求区域前缀和\n",
    "#             for j in range(n):\n",
    "#                 down=ss[i][j-1] if j-1>=0 else 0\n",
    "#                 right=ss[i-1][j] if i-1>=0 else 0\n",
    "#                 topleft=ss[i-1][j-1] if i-1>=0 and j-1>=0 else 0\n",
    "#                 ss[i][j]=down+right-topleft+matrix[i][j]\n",
    "#         su=float(\"-inf\")#-1\n",
    "#         res=[0]*4\n",
    "#         for t in range(m): ### 固定遍历矩形上下边\n",
    "#             # for b in range(t+1,m):\n",
    "#             for b in range(t,m):### 单行也是矩形\n",
    "#                 l=-1\n",
    "#                 for r in range(n): ### 调整矩形右边界\n",
    "#                     topleft=ss[t-1][l-1] if t-1>=0 and l>=0 else 0\n",
    "#                     right=ss[t-1][r] if t-1>=0 else 0\n",
    "#                     down=ss[b][l-1] if l>=0 else 0\n",
    "#                     cur=ss[b][r]+topleft-down-right \n",
    "#                     if cur>su:\n",
    "#                         su=cur \n",
    "#                         res[0]=t\n",
    "#                         res[1]=l+1 \n",
    "#                         res[2]=b\n",
    "#                         res[3]=r\n",
    "#                     # elif cur<0: ### 需要更新左边界case\n",
    "#                     if cur<0:\n",
    "#                         l=r \n",
    "#         return res\n",
    "\n",
    "\n",
    "# # # 作者：Ori\n",
    "# # # 链接：https://leetcode.cn/problems/max-submatrix-lcci/solution/jie-jian-da-lao-si-lu-er-wei-zhuan-yi-we-z9a4/\n",
    "# class Solution:\n",
    "#     def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "#         # 二维数组转变成一维数组求LIS\n",
    "#         n=len(matrix)\n",
    "#         m=len(matrix[0])\n",
    "#         ans=[0]*4 \n",
    "#         # 定义数组求和,二维转一维\n",
    "#         b=[0]*m\n",
    "#         max_sum=matrix[0][0] # 初始化\n",
    "#         r1=c1=0\n",
    "        \n",
    "#         for i in range(n):\n",
    "#             b=[0]*m # 每次循环初始化b\n",
    "#             for j in range(i,n):\n",
    "#                 sum = 0 # 定义dp[i]\n",
    "#                 for k in range(m):\n",
    "#                     b[k]+=matrix[j][k]\n",
    "#                     if sum>0:\n",
    "#                         sum+=b[k]\n",
    "#                     else:\n",
    "#                         sum=b[k] # 说明之前的和小于零需要舍弃，重新开始\n",
    "#                         r1=i\n",
    "#                         c1=k\n",
    "#                     if sum>max_sum:\n",
    "#                         max_sum=sum\n",
    "#                         ans[0]=r1\n",
    "#                         ans[1]=c1\n",
    "#                         ans[2]=j\n",
    "#                         ans[3]=k\n",
    "#         return ans\n",
    "\n",
    "# ### 示例代码\n",
    "# class Solution:\n",
    "#     def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "#         m, n = len(matrix), len(matrix[0])\n",
    "#         pre = [[0]*(n+1) for _ in range(m)]\n",
    "#         for i in range(m):\n",
    "#             for j in range(n):\n",
    "#                 pre[i][j+1] = pre[i][j] + matrix[i][j]\n",
    "#         max_ = matrix[0][0]\n",
    "#         ans = [0,0,0,0]\n",
    "#         for i in range(n):\n",
    "#             for j in range(i,n):\n",
    "#                 # print(i,j,pre[0][j+1] - pre[0][i])\n",
    "#                 tmp_value = 0\n",
    "#                 start_row = 0 \n",
    "#                 for k in range(m):\n",
    "#                     if tmp_value >= 0:\n",
    "#                         tmp_value += pre[k][j+1] - pre[k][i]\n",
    "#                     else:\n",
    "#                         tmp_value = pre[k][j+1] - pre[k][i]\n",
    "#                         start_row = k\n",
    "#                     if tmp_value > max_:\n",
    "#                         ans = [start_row,i,k,j]\n",
    "#                         max_ = tmp_value\n",
    "#         # print(pre,max_)\n",
    "#         return ans\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        precol=[[0]*n for _ in range(m+1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                precol[i+1][j]=precol[i][j]+matrix[i][j]\n",
    "\n",
    "        su=matrix[0][0]\n",
    "        res=[0,0,0,0]\n",
    "        for t in range(m):\n",
    "            tmp=0\n",
    "            # l=0\n",
    "            for b in range(t,m):\n",
    "                cul=0\n",
    "                l=0\n",
    "                for r in range(n):\n",
    "                    if cul>0:\n",
    "                        cul+=precol[b+1][r]-precol[t][r]\n",
    "                    else:\n",
    "                        cul=precol[b+1][r]-precol[t][r]\n",
    "                        l=r\n",
    "                    if cul>su:\n",
    "                        su=cul\n",
    "                        res[0]=t\n",
    "                        res[1]=l\n",
    "                        res[2]=b\n",
    "                        res[3]=r\n",
    "        return res ### 位置要对准\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\r\n",
    "        # 一维：max M[k], M[k] = A[k] + (M[k-1]>=0)\r\n",
    "        ans = [0, 0, 0, 0]\r\n",
    "        M, N = len(matrix), len(matrix[0])\r\n",
    "        maxdp = -inf\r\n",
    "        for i in range(M):\r\n",
    "            # SUM matrix[i:j][]\r\n",
    "            col = [0 for _ in range(N)]\r\n",
    "            for j in range(i, M):\r\n",
    "                dp = 0\r\n",
    "                left = 0\r\n",
    "                for k in range(N):\r\n",
    "                    col[k] += matrix[j][k]\r\n",
    "                    if dp < 0:\r\n",
    "                        left = k\r\n",
    "                        dp = col[k]\r\n",
    "                    else:\r\n",
    "                        dp += col[k]\r\n",
    "                    if dp > maxdp:\r\n",
    "                        ans = [i, left, j, k]\r\n",
    "                        maxdp = dp\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #leetcode 363 代码套路一样\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        Height = len(matrix)\n",
    "        Width = len(matrix[0])\n",
    "        \n",
    "        maxSum = float('-inf')                     #最大面积\n",
    "        res = [0, 0, 0, 0]\n",
    "\n",
    "        for left in range(Width):                     #从左到右，从上到下，滚动遍历\n",
    "            colSum = [0] * Height                      #以left为左边界，每行的总和\n",
    "            for right in range(left, Width):          #这一列每一位为右边界\n",
    "                for i in range(Height):                #遍历列中每一位，计算前缀和\n",
    "                    colSum[i] += matrix[i][right]\n",
    "\n",
    "                startX, endX, maxSumCur= self.getMax(colSum)#在left，right为边界下的矩阵中，前缀和colSum的最大值\n",
    "                if maxSumCur > maxSum:\n",
    "                    res = [startX, left, endX, right]        #left是起点y轴坐标，right是终点y轴坐标\n",
    "                    maxSum = maxSumCur\n",
    "        return res\n",
    "    \n",
    "    #这一列中，找最大值，同时记录起点，终点\n",
    "    #因为传进来的是列的前缀和，所以返回的起点、终点代表的是行坐标\n",
    "    def getMax(self, nums):\n",
    "        n = len(nums)\n",
    "        maxVal, curSum = nums[0], nums[0]       #初始化最大值\n",
    "        startIndex, end, start = 0, 0, 0        #初始化临时起点，起点，终点\n",
    "        for i in range(1,n):\n",
    "            if curSum<0:                        #前缀和小于0了，前面就不要了，从当前开始\n",
    "                curSum = nums[i]\n",
    "                startIndex = i                  #前面的前缀和小于0了，需要重置起点，从当前开始才有可能成为最大值\n",
    "            else:\n",
    "                curSum = curSum + nums[i]\n",
    "            \n",
    "            if curSum > maxVal:\n",
    "                maxVal = curSum\n",
    "                start = startIndex             #记录下前面的起点，默认0，或者是curSum<0后，重新更新的起点\n",
    "                end = i                        #终点是当前坐标\n",
    "        return start, end, maxVal              #起点，终点，最大前缀和（最大面积）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n=len(matrix)\n",
    "        m=len(matrix[0])\n",
    "        ans=[0]*4\n",
    "        b=[0]*m\n",
    "        max_sum=matrix[0][0]\n",
    "        r1=c1=0\n",
    "        for i in range(n):\n",
    "            b=[0]*m\n",
    "            for j in range(i,n):\n",
    "                sum=0\n",
    "                for k in range(m):\n",
    "                    b[k]+=matrix[j][k]\n",
    "                    if sum>0:\n",
    "                        sum+=b[k]\n",
    "                    else:\n",
    "                        sum=b[k]\n",
    "                        r1=i\n",
    "                        c1=k\n",
    "                    if sum>max_sum:\n",
    "                        max_sum=sum\n",
    "                        ans=[r1,c1,j,k]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\r\n",
    "        # 一维：max M[k], M[k] = A[k] + (M[k-1]>=0)\r\n",
    "        ans = [0, 0, 0, 0]\r\n",
    "        M, N = len(matrix), len(matrix[0])\r\n",
    "        maxdp = -inf\r\n",
    "        for i in range(M):\r\n",
    "            # SUM matrix[i:j][]\r\n",
    "            col = [0 for _ in range(N)]\r\n",
    "            for j in range(i, M):\r\n",
    "                dp = 0\r\n",
    "                left = 0\r\n",
    "                for k in range(N):\r\n",
    "                    col[k] += matrix[j][k]\r\n",
    "                    if dp < 0:\r\n",
    "                        left = k\r\n",
    "                        dp = col[k]\r\n",
    "                    else:\r\n",
    "                        dp += col[k]\r\n",
    "                    if dp > maxdp:\r\n",
    "                        ans = [i, left, j, k]\r\n",
    "                        maxdp = dp\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        # 一维：max M[k], M[k] = A[k] + (M[k-1]>=0)\n",
    "        ans = [0, 0, 0, 0]\n",
    "        M, N = len(matrix), len(matrix[0])\n",
    "        maxdp = -inf\n",
    "        for i in range(M):\n",
    "            # SUM matrix[i:j][]\n",
    "            col = [0 for _ in range(N)]\n",
    "            for j in range(i, M):\n",
    "                dp = 0\n",
    "                left = 0\n",
    "                for k in range(N):\n",
    "                    col[k] += matrix[j][k]\n",
    "                    if dp < 0:\n",
    "                        left = k\n",
    "                        dp = col[k]\n",
    "                    else:\n",
    "                        dp += col[k]\n",
    "                    if dp > maxdp:\n",
    "                        ans = [i, left, j, k]\n",
    "                        maxdp = dp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        ans = [0]*4\n",
    "        r1,c1,r2,c2 = [0]*4\n",
    "        max_sum = matrix[0][0]\n",
    "        for i in range(m):\n",
    "            total = [0]*n\n",
    "            for j in range(i,m):\n",
    "                cur_max = 0\n",
    "                for k in range(n):\n",
    "                    total[k] += matrix[j][k]\n",
    "                    if cur_max>0:\n",
    "                        cur_max+=total[k]\n",
    "                    else:\n",
    "                        cur_max = total[k]\n",
    "                        r1 = i\n",
    "                        c1 = k\n",
    "                    if cur_max>max_sum:\n",
    "                        r2,c2=j,k\n",
    "                        max_sum = cur_max\n",
    "                        ans = r1,c1,r2,c2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        a=[0]*n\n",
    "        ans = [0]*4        \n",
    "        max_dp = float('-inf')\n",
    "\n",
    "        for i in range(m):\n",
    "            for k in range(n): a[k] = 0\n",
    "            for j in range(i, m):\n",
    "                dp = 0\n",
    "                begin = 0\n",
    "                for k in range(n):\n",
    "                    a[k] += matrix[j][k]\n",
    "                    if dp <= 0:\n",
    "                        dp = a[k]\n",
    "                        begin = k\n",
    "                    else:\n",
    "                        dp += a[k]\n",
    "                    if dp > max_dp:\n",
    "                        max_dp = dp\n",
    "                        ans = [i, begin, j,k]\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #leetcode 363 代码套路一样\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "        maxArea = float('-inf')                     #最大面积\n",
    "        res = [0, 0, 0, 0]\n",
    "\n",
    "        for left in range(col):                     #从左到右，从上到下，滚动遍历\n",
    "            colSum = [0] * row                      #以left为左边界，每行的总和\n",
    "            for right in range(left, col):          #这一列每一位为右边界\n",
    "                for i in range(row):                #遍历列中每一位，计算前缀和\n",
    "                    colSum[i] += matrix[i][right]\n",
    "\n",
    "                startX, endX, maxAreaCur= self.getMax(colSum)#在left，right为边界下的矩阵中，前缀和colSum的最大值\n",
    "                if maxAreaCur > maxArea:\n",
    "                    res = [startX, left, endX, right]        #left是起点y轴坐标，right是终点y轴坐标\n",
    "                    maxArea = maxAreaCur\n",
    "        return res\n",
    "    \n",
    "    #这一列中，找最大值，同时记录起点，终点\n",
    "    #因为传进来的是列的前缀和，所以返回的起点、终点代表的是行坐标\n",
    "    def getMax(self, nums):\n",
    "        n = len(nums)\n",
    "        maxVal, curSum = nums[0], nums[0]       #初始化最大值\n",
    "        startIndex, end, start = 0, 0, 0        #初始化临时起点，起点，终点\n",
    "        for i in range(1,n):\n",
    "            if curSum<0:                        #前缀和小于0了，前面就不要了，从当前开始\n",
    "                curSum = nums[i]\n",
    "                startIndex = i                  #前面的前缀和小于0了，需要重置起点，从当前开始才有可能成为最大值\n",
    "            else:\n",
    "                curSum = curSum + nums[i]\n",
    "            \n",
    "            if curSum > maxVal:\n",
    "                maxVal = curSum\n",
    "                start = startIndex             #记录下前面的起点，默认0，或者是curSum<0后，重新更新的起点\n",
    "                end = i                        #终点是当前坐标\n",
    "        return start, end, maxVal              #起点，终点，最大前缀和（最大面积）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        a, b, c, d = 0,0,0,0\n",
    "        ans = float('-inf')\n",
    "        for up in range(0, len(matrix)):\n",
    "            helpArr = [0] * len(matrix[0])\n",
    "            for down in range(up, len(matrix)):\n",
    "                pre = float('-inf')\n",
    "                l = 0\n",
    "                r = 0\n",
    "                while r < len(matrix[0]):\n",
    "                    helpArr[r] += matrix[down][r]\n",
    "                    if pre >= 0:\n",
    "                        pre += helpArr[r]\n",
    "                    else:\n",
    "                        pre = helpArr[r]\n",
    "                        l = r\n",
    "                    if pre > ans:\n",
    "                        ans = pre\n",
    "                        a = up\n",
    "                        b = l\n",
    "                        c = down\n",
    "                        d = r\n",
    "                    r += 1\n",
    "        return [a, b, c, d]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        col_sum = [0] * n\n",
    "        max_sum = -float('inf')\n",
    "        r1, c1, r2, c2 = 0, 0, 0, 0\n",
    "        for i in range(m):\n",
    "            col_sum = [0] * n\n",
    "            for j in range(i, -1, -1):\n",
    "                for col in range(n):\n",
    "                    col_sum[col] += matrix[j][col]\n",
    "                (begin_col, end_col), cur_sum = self.max_sub_arr(col_sum)\n",
    "                if max_sum < cur_sum:\n",
    "                    max_sum = cur_sum\n",
    "                    r1 = j\n",
    "                    c1 = begin_col\n",
    "                    r2 = i\n",
    "                    c2 = end_col\n",
    "        return [r1, c1, r2, c2]\n",
    "\n",
    "            \n",
    "\n",
    "    def max_sub_arr(self, nums):\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "        dp[0] = nums[0]\n",
    "        \n",
    "        max_sum = nums[0]\n",
    "        res = [0, 0]\n",
    "        begin = 0\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if dp[i-1] < 0:\n",
    "                begin = i\n",
    "                dp[i] = nums[i]\n",
    "            else:\n",
    "                dp[i] = dp[i-1] + nums[i]\n",
    "            if dp[i] > max_sum:\n",
    "                max_sum = dp[i]\n",
    "                res[0] = begin\n",
    "                res[1] = i\n",
    "        return res, max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        max_result = [0,0,0,0]\n",
    "        max_sum = matrix[0][0]\n",
    "        start_i,start_j = 0,0\n",
    "\n",
    "\n",
    "        for i in range(m):\n",
    "            total = [0] * n\n",
    "            for end_i in range(i, m):\n",
    "                cur_max = 0\n",
    "                for end_j in range(n):\n",
    "                    total[end_j] += matrix[end_i][end_j]\n",
    "                    if cur_max > 0:\n",
    "                        cur_max += total[end_j] \n",
    "                    else: # cur_max + total[end_j] <= cur_max 加了变得更小了\n",
    "                        cur_max = total[end_j] # 那就不用加了\n",
    "                        start_i,start_j = i, end_j\n",
    "                    if cur_max > max_sum: # 如果当前和比全局最大和大了\n",
    "                        max_sum = cur_max \n",
    "                        max_result = [start_i,start_j ,end_i, end_j] # 更新结果\n",
    "\n",
    "        return max_result\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #leetcode 363 代码套路一样\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "        maxArea = float('-inf')                     #最大面积\n",
    "        res = [0, 0, 0, 0]\n",
    "\n",
    "        for left in range(col):                     #从左到右，从上到下，滚动遍历\n",
    "            colSum = [0] * row                      #以left为左边界，每行的总和\n",
    "            for right in range(left, col):          #这一列每一位为右边界\n",
    "                for i in range(row):                #遍历列中每一位，计算前缀和\n",
    "                    colSum[i] += matrix[i][right]\n",
    "\n",
    "                startX, endX, maxAreaCur= self.getMax(colSum)#在left，right为边界下的矩阵中，前缀和colSum的最大值\n",
    "                if maxAreaCur > maxArea:\n",
    "                    res = [startX, left, endX, right]        #left是起点y轴坐标，right是终点y轴坐标\n",
    "                    maxArea = maxAreaCur\n",
    "        return res\n",
    "    \n",
    "    #这一列中，找最大值，同时记录起点，终点\n",
    "    #因为传进来的是列的前缀和，所以返回的起点、终点代表的是行坐标\n",
    "    def getMax(self, nums):\n",
    "        n = len(nums)\n",
    "        maxVal, curSum = nums[0], nums[0]       #初始化最大值\n",
    "        startIndex, end, start = 0, 0, 0        #初始化临时起点，起点，终点\n",
    "        for i in range(1,n):\n",
    "            if curSum<0:                        #前缀和小于0了，前面就不要了，从当前开始\n",
    "                curSum = nums[i]\n",
    "                startIndex = i                  #前面的前缀和小于0了，需要重置起点，从当前开始才有可能成为最大值\n",
    "            else:\n",
    "                curSum = curSum + nums[i]\n",
    "            \n",
    "            if curSum > maxVal:\n",
    "                maxVal = curSum\n",
    "                start = startIndex             #记录下前面的起点，默认0，或者是curSum<0后，重新更新的起点\n",
    "                end = i                        #终点是当前坐标\n",
    "        return start, end, maxVal              #起点，终点，最大前缀和（最大面积）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        a, b, c, d = 0,0,0,0\n",
    "        ans = float('-inf')\n",
    "        for up in range(0, len(matrix)):\n",
    "            helpArr = [0] * len(matrix[0])\n",
    "            for down in range(up, len(matrix)):\n",
    "                pre = float('-inf')\n",
    "                l = 0\n",
    "                r = 0\n",
    "                while r < len(matrix[0]):\n",
    "                    helpArr[r] += matrix[down][r]\n",
    "                    if pre >= 0:\n",
    "                        pre += helpArr[r]\n",
    "                    else:\n",
    "                        pre = helpArr[r]\n",
    "                        l = r\n",
    "                    if pre > ans:\n",
    "                        ans = pre\n",
    "                        a = up\n",
    "                        b = l\n",
    "                        c = down\n",
    "                        d = r\n",
    "                    r += 1\n",
    "        return [a, b, c, d]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #leetcode 363 代码套路一样\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "        maxArea = float('-inf')                     #最大面积\n",
    "        res = [0, 0, 0, 0]\n",
    "\n",
    "        for left in range(col):                     #从左到右，从上到下，滚动遍历\n",
    "            colSum = [0] * row                      #以left为左边界，每行的总和\n",
    "            for right in range(left, col):          #这一列每一位为右边界\n",
    "                for i in range(row):                #遍历列中每一位，计算前缀和\n",
    "                    colSum[i] += matrix[i][right]\n",
    "\n",
    "                startX, endX, maxAreaCur= self.getMax(colSum)#在left，right为边界下的矩阵中，前缀和colSum的最大值\n",
    "                if maxAreaCur > maxArea:\n",
    "                    res = [startX, left, endX, right]        #left是起点y轴坐标，right是终点y轴坐标\n",
    "                    maxArea = maxAreaCur\n",
    "        return res\n",
    "    \n",
    "    #这一列中，找最大值，同时记录起点，终点\n",
    "    #因为传进来的是列的前缀和，所以返回的起点、终点代表的是行坐标\n",
    "    def getMax(self, nums):\n",
    "        n = len(nums)\n",
    "        maxVal, curSum = nums[0], nums[0]       #初始化最大值\n",
    "        startIndex, end, start = 0, 0, 0        #初始化临时起点，起点，终点\n",
    "        for i in range(1,n):\n",
    "            if curSum<0:                        #前缀和小于0了，前面就不要了，从当前开始\n",
    "                curSum = nums[i]\n",
    "                startIndex = i                  #前面的前缀和小于0了，需要重置起点，从当前开始才有可能成为最大值\n",
    "            else:\n",
    "                curSum = curSum + nums[i]\n",
    "            \n",
    "            if curSum > maxVal:\n",
    "                maxVal = curSum\n",
    "                start = startIndex             #记录下前面的起点，默认0，或者是curSum<0后，重新更新的起点\n",
    "                end = i                        #终点是当前坐标\n",
    "        return start, end, maxVal              #起点，终点，最大前缀和（最大面积）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        res = [0,0,0,0]\n",
    "        max_area = -inf\n",
    "\n",
    "        for up in range(m):\n",
    "            cumSum = [0]*n\n",
    "            for down in range(up,m):\n",
    "                for right in range(n):\n",
    "                    cumSum[right]+=matrix[down][right]\n",
    "                start,end,area = self.getMax(cumSum)\n",
    "                if area>max_area:\n",
    "                    res = [up,start,down,end]\n",
    "                    max_area = area\n",
    "        return res\n",
    "\n",
    "    def getMax(self,nums):\n",
    "        prefix = 0\n",
    "        res = -inf\n",
    "        leftIndex,start,end = 0,0,0\n",
    "        for i in range(len(nums)):\n",
    "            prefix+=nums[i]\n",
    "            if prefix<nums[i]:\n",
    "                prefix = nums[i]\n",
    "                leftIndex = i\n",
    "            if prefix>res:\n",
    "                res = prefix\n",
    "                start = leftIndex\n",
    "                end = i\n",
    "        return start,end,res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        res = -inf\n",
    "        ans = [0,0,0,0]\n",
    "\n",
    "        def prefixSum(nums):\n",
    "            prefix = 0\n",
    "            n = len(nums)\n",
    "            start,res_start,res_end = 0,0,0\n",
    "            res = -inf\n",
    "            for i in range(n):\n",
    "                prefix+=nums[i]\n",
    "                if prefix<nums[i]:\n",
    "                    start = i\n",
    "                    prefix = nums[i]\n",
    "                if prefix>res:\n",
    "                    res_start = start\n",
    "                    res_end = i\n",
    "                    res = prefix\n",
    "            return res_start,res_end,res\n",
    "        \n",
    "        for x in range(m):\n",
    "            prefix = [0]*n\n",
    "            for i in range(x,m):\n",
    "                for j in range(n):\n",
    "                    prefix[j]+=matrix[i][j]\n",
    "                start,end,sum = prefixSum(prefix)\n",
    "                if sum>res:\n",
    "                    ans = [x,start,i,end]\n",
    "                    res = sum\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        max_s = -inf\n",
    "        r1 = c1 = r2 = c2 = -1\n",
    "        for i in range(m):\n",
    "            b = [0 for _ in range(n)]\n",
    "            for j in range(i, m):\n",
    "                s = -inf\n",
    "                begin = 0\n",
    "                for k in range(n):\n",
    "                    b[k] += matrix[j][k]\n",
    "                    if s > 0:\n",
    "                        s += b[k]\n",
    "                    else:\n",
    "                        s = b[k]\n",
    "                        begin = k\n",
    "                    if s > max_s:\n",
    "                        max_s = s\n",
    "                        r1, r2, c1, c2 = i, j, begin, k\n",
    "        return [r1, c1, r2, c2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#最大子矩阵，动态规划\n",
    "#输入matrix =[[9,-8,1,3,-2],[-3,7,6,-2,4],[6,-4,-4,8,-7]]输出[0,0,2,3]\n",
    "#输入：[   [-1,0],   [0,-1]]输出：[0,1,0,1]\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        #降维后，类似求最大子序列和\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        ans=[0]*4\n",
    "        r1,c1,r2,c2=[0]*4\n",
    "        max_sum=matrix[0][0]#初始化全局最大和\n",
    "        for i in range(m):#起始行\n",
    "            total=[0]*n#初始化一个长度为n的一维列表来记录所有压缩的列和\n",
    "            for j in range(i,m):\n",
    "                cur_max=0\n",
    "                for k in range(n):\n",
    "                    total[k]+=matrix[j][k]\n",
    "                    if cur_max>0:cur_max+=total[k]\n",
    "                    else:\n",
    "                        cur_max=total[k]\n",
    "                        r1,c1=i,k#更新行起点和列起点\n",
    "                    if cur_max>max_sum:\n",
    "                        max_sum=cur_max\n",
    "                        r2,c2=j,k\n",
    "                        ans=r1,c1,r2,c2 \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #leetcode 363 代码套路一样\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "        maxArea = float('-inf')                     #最大面积\n",
    "        res = [0, 0, 0, 0]\n",
    "\n",
    "        for left in range(col):                     #从左到右，从上到下，滚动遍历\n",
    "            colSum = [0] * row                      #以left为左边界，每行的总和\n",
    "            for right in range(left, col):          #这一列每一位为右边界\n",
    "                for i in range(row):                #遍历列中每一位，计算前缀和\n",
    "                    colSum[i] += matrix[i][right]\n",
    "\n",
    "                startX, endX, maxAreaCur= self.getMax(colSum)#在left，right为边界下的矩阵中，前缀和colSum的最大值\n",
    "                if maxAreaCur > maxArea:\n",
    "                    res = [startX, left, endX, right]        #left是起点y轴坐标，right是终点y轴坐标\n",
    "                    maxArea = maxAreaCur\n",
    "        return res\n",
    "    \n",
    "    #这一列中，找最大值，同时记录起点，终点\n",
    "    #因为传进来的是列的前缀和，所以返回的起点、终点代表的是行坐标\n",
    "    def getMax(self, nums):\n",
    "        n = len(nums)\n",
    "        maxVal, curSum = nums[0], nums[0]       #初始化最大值\n",
    "        startIndex, end, start = 0, 0, 0        #初始化临时起点，起点，终点\n",
    "        for i in range(1,n):\n",
    "            if curSum<0:                        #前缀和小于0了，前面就不要了，从当前开始\n",
    "                curSum = nums[i]\n",
    "                startIndex = i                  #前面的前缀和小于0了，需要重置起点，从当前开始才有可能成为最大值\n",
    "            else:\n",
    "                curSum = curSum + nums[i]\n",
    "            \n",
    "            if curSum > maxVal:\n",
    "                maxVal = curSum\n",
    "                start = startIndex             #记录下前面的起点，默认0，或者是curSum<0后，重新更新的起点\n",
    "                end = i                        #终点是当前坐标\n",
    "        return start, end, maxVal              #起点，终点，最大前缀和（最大面积）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        max_s = -inf\n",
    "        r1 = c1 = r2 = c2 = -1\n",
    "        for i in range(m):\n",
    "            b = [0 for _ in range(n)]\n",
    "            for j in range(i, m):\n",
    "                s = -inf\n",
    "                begin = 0\n",
    "                for k in range(n):\n",
    "                    b[k] += matrix[j][k]\n",
    "                    if s > 0:\n",
    "                        s += b[k]\n",
    "                    else:\n",
    "                        s = b[k]\n",
    "                        begin = k\n",
    "                    if s > max_s:\n",
    "                        max_s = s\n",
    "                        r1, r2, c1, c2 = i, j, begin, k\n",
    "        return [r1, c1, r2, c2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\r\n",
    "        def getMaxSubsequenceSum(seq):                # 求seq中的最大子序和, 并返回起始/终止下标\r\n",
    "            cum_sum = max_sum = seq[0]\r\n",
    "            max_s_idx, max_e_idx = 0, 0\r\n",
    "            s_idx = 0\r\n",
    "            for i in range(1, len(seq)):\r\n",
    "                if cum_sum >= 0:\r\n",
    "                    cum_sum += seq[i]\r\n",
    "                else:\r\n",
    "                    cum_sum = seq[i]\r\n",
    "                    s_idx = i\r\n",
    "                if cum_sum > max_sum:\r\n",
    "                    max_sum = cum_sum\r\n",
    "                    max_s_idx = s_idx\r\n",
    "                    max_e_idx = i\r\n",
    "            return max_sum, max_s_idx, max_e_idx\r\n",
    "\r\n",
    "        res = [-1] * 4\r\n",
    "        n, m = len(matrix), len(matrix[0])\r\n",
    "        max_sum = float('-inf')\r\n",
    "\r\n",
    "        for row_s in range(n):               # 起始行row_s\r\n",
    "            col_sum = [0] * m                # col_sum[j]记录从第i行~第i_end行, 各列元素的前缀和. \r\n",
    "\r\n",
    "            for row_e in range(row_s, n):    # 枚举终止行row_e\r\n",
    "                for j in range(m):\r\n",
    "                    col_sum[j] += matrix[row_e][j]   # col_sum可由前缀和的方式计算得到. \r\n",
    "                \r\n",
    "                cur_sum, col_s, col_e = getMaxSubsequenceSum(col_sum)   # 求得col_sum中的最大子序和, 以及起始终止下标\r\n",
    "                if cur_sum > max_sum:\r\n",
    "                    res[0], res[1], res[2], res[3] = row_s, col_s, row_e, col_e\r\n",
    "                    max_sum = cur_sum\r\n",
    "        return res\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\r\n",
    "\r\n",
    "        res = [-1] * 4\r\n",
    "        n, m = len(matrix), len(matrix[0])\r\n",
    "        max_sum = float('-inf')\r\n",
    "\r\n",
    "        for row_s in range(n):               # 起始行row_s\r\n",
    "            col_sum = [0] * m                # col_sum[j]记录从第i行~第i_end行, 各列元素的前缀和. \r\n",
    "\r\n",
    "            for row_e in range(row_s, n):    # 枚举终止行row_e\r\n",
    "                # 求得row_s与row_e行之间, col_sum中的最大子序和, 以及起始终止下标.\r\n",
    "                cum_sum = 0\r\n",
    "                s_idx = 0\r\n",
    "                for j in range(m):\r\n",
    "                    col_sum[j] += matrix[row_e][j]   # col_sum可由前缀和的方式计算得到. \r\n",
    "                    if cum_sum >= 0:\r\n",
    "                        cum_sum += col_sum[j]\r\n",
    "                    else:\r\n",
    "                        cum_sum = col_sum[j]\r\n",
    "                        s_idx = j\r\n",
    "                    \r\n",
    "                    if cum_sum > max_sum:\r\n",
    "                        res[0], res[1], res[2], res[3] = row_s, s_idx, row_e, j\r\n",
    "                        max_sum = cum_sum\r\n",
    "        return res\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix):\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        # 记录当前i~j行组成大矩阵的每一列的和，将二维转化为一维\n",
    "        b = [0] * n\n",
    "        max_sum = -inf\n",
    "        ans = [0, 0, 0, 0]\n",
    "        # 记录左上角\n",
    "        start = [0, 0]\n",
    "        for i in range(m):\n",
    "            b = [0] * n\n",
    "            for j in range(i, m):\n",
    "                sum_ = 0\n",
    "                for k in range(n):\n",
    "                    b[k] += matrix[j][k]\n",
    "                    if sum_ > 0:\n",
    "                        sum_ += b[k]\n",
    "                    else:\n",
    "                        sum_ = b[k]\n",
    "                        start = [i, k]\n",
    "                    if sum_ > max_sum:\n",
    "                        max_sum = sum_\n",
    "                        ans = [start[0], start[1], j, k]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return []\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        pre_arr = [[0 for j in range(m)] for i in range( n +1)]\n",
    "        for i in range(1 , n +1):\n",
    "            for j in range(m):\n",
    "                pre_arr[i][j] = pre_arr[ i -1][j] + matrix[ i -1][j]\n",
    "        def getGap(i, j):\n",
    "            res = [0 for k in range(m)]\n",
    "            for t in range(m):\n",
    "                res[t] =  pre_arr[ j +1][t] - pre_arr[i][t]\n",
    "            return res\n",
    "\n",
    "        \n",
    "        data = -float('inf')\n",
    "        def getMaxOneSquire(arr):\n",
    "            m_x = -float('inf')\n",
    "            n = len(arr)\n",
    "            max_end = 0\n",
    "            begin = 0\n",
    "            max_begin = 0\n",
    "            curr_sum = -float('inf')\n",
    "            for i in range(0 , n):\n",
    "                if curr_sum < 0:\n",
    "                    curr_sum = arr[i]\n",
    "                    begin = i\n",
    "                else:\n",
    "                    curr_sum = curr_sum + arr[i]\n",
    "                if curr_sum > m_x:\n",
    "                    m_x = curr_sum\n",
    "                    max_begin = begin\n",
    "                    max_end = i\n",
    "\n",
    "            return m_x, max_begin, max_end\n",
    "\n",
    "        r1 ,r2 ,c1 ,c2 = 0 , 0 , 0 ,0\n",
    "        for j in range(n):\n",
    "            for i in range( j +1):\n",
    "                p =  getGap(i ,j)\n",
    "                t, l1, l2 = getMaxOneSquire(p)\n",
    "                if t > data:\n",
    "                    data = t\n",
    "                    c1 ,c2 = l1, l2\n",
    "                    r1 ,r2 = i, j\n",
    "        return [r1 ,c1 ,r2 ,c2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix):\n",
    "        \"\"\"\n",
    "        取得二维矩阵中最大子矩阵的位置\n",
    "        Args:\n",
    "            matrix (list[list[int]]): 待搜索二维矩阵\n",
    "        returns (list[int]): 最大子矩阵的左上角和右下角坐标\n",
    "        \"\"\"\n",
    "        #处理异常情况\n",
    "        if matrix == None or len(matrix) == 0:\n",
    "            return []\n",
    "\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = [0, 0, 0, 0]  #子矩阵坐标\n",
    "        ans_max = -float(\"inf\")\n",
    "        print(\"开始遍历\")\n",
    "\n",
    "        #分别遍历将二维矩阵压缩为数组, 0-0, 0-1, 0-2, 0-3, 1-1, 1-2....4-4行下的子矩阵的最大子矩阵, 每次调用一次数组最大累加和\n",
    "        for i in range(m):\n",
    "            for j in range(i, m):\n",
    "                if j == i:\n",
    "                    cur_arr = [num for num in matrix[i]]    #创建累加和矩阵\n",
    "                else:\n",
    "                    #第i~j行构成的数组\n",
    "                    for k in range(n):\n",
    "                        cur_arr[k] += matrix[j][k]  \n",
    "                \n",
    "                cur_max, start, end = self.maxSubArray(cur_arr)\n",
    "                if cur_max > ans_max:\n",
    "                    ans_max = cur_max\n",
    "                    ans = [i, start, j, end]\n",
    "                \n",
    "                print(\"此时的i, j\", i, j)\n",
    "                if i == 0 and j == 2:\n",
    "                    print(\"此时的数组arr:\", cur_arr)\n",
    "\n",
    "        return ans \n",
    "\n",
    "\n",
    "    def maxSubArray(self, arr):\n",
    "        \"\"\"\n",
    "        取得数组中的最大累加和\n",
    "        Args:\n",
    "            arr (list[int]): 目标数组\n",
    "        returns: 最大累加和, 最大累加和字串在原数组中的起始位置和结束位置\n",
    "        \"\"\"\n",
    "        if arr == None or len(arr) == 0:\n",
    "            return 0, 0, 0 \n",
    "\n",
    "        n = len(arr)\n",
    "        \n",
    "        #dp[i]的定义表示已arr[i]为(字串结尾的最大累加和, 子串的长度)\n",
    "        dp = [[num, 1] for num in arr]  \n",
    "        ans = arr[0]\n",
    "        ans_idx = [0, 0]\n",
    "        start, end = 0, 0 \n",
    "\n",
    "        for i in range(1, n):\n",
    "            if arr[i] + dp[i - 1][0] > dp[i][0]:\n",
    "                dp[i][0] = arr[i] + dp[i - 1][0]\n",
    "                dp[i][1] = dp[i - 1][1] + 1\n",
    "            if dp[i][0] > ans:\n",
    "                ans = dp[i][0]\n",
    "                ans_idx = [i - dp[i][1] + 1, i]\n",
    "        \n",
    "        return ans, ans_idx[0], ans_idx[1]\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        def lis(nums): #返回nums数组的最大连续子数组的开头和结尾, 单独一个数也可以\n",
    "            pre = nums[0]\n",
    "            x, y = 0, 0\n",
    "            Max = pre\n",
    "            ls = [Max, 0, 0, 0, 0]\n",
    "            for i in range(1, len(nums)):\n",
    "                if pre>=0:\n",
    "                    pre += nums[i]\n",
    "                    y += 1\n",
    "                else:\n",
    "                    pre = nums[i]\n",
    "                    x, y =i, i\n",
    "                if Max<pre:\n",
    "                    Max = pre\n",
    "                    ls[0], ls[2], ls[4] = Max, x, y\n",
    "            # print(nums, ls)\n",
    "            return ls\n",
    "        def preSum(matrix):\n",
    "            pre = [[0]*n for _ in range(m+1)]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    pre[i+1][j] = pre[i][j]+matrix[i][j]\n",
    "            return pre\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [0]*n\n",
    "        res = []\n",
    "        pre = preSum(matrix)\n",
    "        for i in range(m):\n",
    "            for j in range(i, m):\n",
    "                dp = []\n",
    "                for k in range(n):\n",
    "                    dp.append(pre[j+1][k]-pre[i][k])\n",
    "                ls = lis(dp)\n",
    "                ls[1], ls[3] = i, j\n",
    "                res.append(ls)\n",
    "\n",
    "        # print(res)\n",
    "        res.sort(key=lambda x:-x[0])\n",
    "        # print(res)\n",
    "        return res[0][1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        prefix = [[] for _ in range(n)]\n",
    "        for j in range(n):\n",
    "            res = 0\n",
    "            for i in range(m):\n",
    "                res += matrix[i][j]\n",
    "                prefix[j].append(res)\n",
    "        max_1 = float('-inf')\n",
    "        result = []\n",
    "        for i1 in range(m):\n",
    "            for i2 in range(i1, m):\n",
    "                ans = []\n",
    "                for j in range(n):\n",
    "                    if i1 > 0:\n",
    "                        ans.append(prefix[j][i2] - prefix[j][i1 - 1])\n",
    "                    else:\n",
    "                        ans.append(prefix[j][i2])\n",
    "                begin = 0\n",
    "                l = 0\n",
    "                res = 0\n",
    "                max_2 = float('-inf')\n",
    "                for k in range(n):\n",
    "                    if res < 0:\n",
    "                        l = k\n",
    "                        res = ans[k]\n",
    "                    else:\n",
    "                        res += ans[k]\n",
    "                    if res > max_2:\n",
    "                        begin = l \n",
    "                        end = k\n",
    "                        max_2 = res\n",
    "                if max_2 > max_1:\n",
    "                    result = [i1, begin, i2, end]\n",
    "                    max_1 = max_2\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        def lis(nums): #返回nums数组的最大连续子数组的开头和结尾, 单独一个数也可以\n",
    "            pre = nums[0]\n",
    "            x, y = 0, 0\n",
    "            Max = pre\n",
    "            ls = [Max, 0, 0, 0, 0]\n",
    "            for i in range(1, len(nums)):\n",
    "                if pre>=0:\n",
    "                    pre += nums[i]\n",
    "                    y += 1\n",
    "                else:\n",
    "                    pre = nums[i]\n",
    "                    x, y =i, i\n",
    "                if Max<pre:\n",
    "                    Max = pre\n",
    "                    ls[0], ls[2], ls[4] = Max, x, y\n",
    "            # print(nums, ls)\n",
    "            return ls\n",
    "        def preSum(matrix):\n",
    "            pre = [[0]*n for _ in range(m+1)]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    pre[i+1][j] = pre[i][j]+matrix[i][j]\n",
    "            return pre\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [0]*n\n",
    "        res = []\n",
    "        pre = preSum(matrix)\n",
    "        for i in range(m):\n",
    "            for j in range(i, m):\n",
    "                dp = []\n",
    "                for k in range(n):\n",
    "                    dp.append(pre[j+1][k]-pre[i][k])\n",
    "                ls = lis(dp)\n",
    "                ls[1], ls[3] = i, j\n",
    "                res.append(ls)\n",
    "\n",
    "        # print(res)\n",
    "        res.sort(key=lambda x:-x[0])\n",
    "        # print(res)\n",
    "        return res[0][1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "思路：前缀和预处理+最大子数组和动态规划\n",
    "1. 预处理，每一列求前缀和\n",
    "2. 枚举两行i和j，将第i行和第j行之间的元素按列求和，得到一个数组\n",
    "    2.1 求数组的最大子数组和\n",
    "3. 返回所有数组中最大的子数组和\n",
    "时间复杂度：O(n^2d)\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n, d = len(matrix), len(matrix[0])\n",
    "\n",
    "        pre_sum = [[0] * d for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(d):\n",
    "                if i == 0:\n",
    "                    pre_sum[i][j] = matrix[i][j]\n",
    "                else:\n",
    "                    pre_sum[i][j] = pre_sum[i-1][j] + matrix[i][j]\n",
    "        \n",
    "\n",
    "        max_sum = -inf\n",
    "        begin = None\n",
    "        end = None\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                temp = [pre_sum[j][x]-pre_sum[i][x]+matrix[i][x] for x in range(d)]\n",
    "                cur = 0\n",
    "                l = 0\n",
    "                for r, item in enumerate(temp):\n",
    "                    if cur < 0:\n",
    "                        cur = item\n",
    "                        l = r\n",
    "                    else:\n",
    "                        cur += item\n",
    "                    if cur > max_sum:\n",
    "                        max_sum = cur\n",
    "                        begin = [i, l]\n",
    "                        end = [j, r]\n",
    "        return begin + end\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，\n",
    "r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。\n",
    "\"\"\"\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n: int = len(matrix)\n",
    "        m: int = len(matrix[0])\n",
    "        ans = [0, 0, 0, 0]\n",
    "        best = float('-inf')\n",
    "        s = [[0] * (m + 1) for _ in range(n)]  # 每一行的前缀和 [0, a1, a2, ...]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                s[i][j + 1] = s[i][j] + matrix[i][j]\n",
    "        for i in range(m):  # i,j卡两列之间\n",
    "            for j in range(i, m):\n",
    "                f = 0\n",
    "                r1 = 0\n",
    "                for k in range(n):  # 每一行\n",
    "                    if f < 0:\n",
    "                        f = s[k][j + 1] - s[k][i]\n",
    "                        r1 = k\n",
    "                    else:\n",
    "                        f += s[k][j + 1] - s[k][i]\n",
    "                    if f > best:\n",
    "                        best = f\n",
    "                        ans = [r1, i, k, j]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        # 连续子数组最大和\n",
    "        maximum=nums[0]\n",
    "        temp=nums[0]\n",
    "        left=begin=right=0\n",
    "        for i in range(1,len(nums)):\n",
    "            if temp>0:\n",
    "                temp+=nums[i]\n",
    "            else:\n",
    "                temp=nums[i]\n",
    "                begin=i\n",
    "            if temp>maximum:\n",
    "                maximum=temp\n",
    "                left=begin\n",
    "                right=i\n",
    "        return maximum,left,right\n",
    "\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        # 第一步，计算前缀和\n",
    "        m=len(matrix)\n",
    "        n=len(matrix[0])\n",
    "        prefix=[[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        for i in range(m):\n",
    "            summ=0\n",
    "            for j in range(n):\n",
    "                summ+=matrix[i][j]\n",
    "                prefix[i+1][j+1]=summ\n",
    "\n",
    "        maximum=-2147483647\n",
    "        ans=[0,0,0,0]\n",
    "        for j in range(n):\n",
    "            for k in range(j+1,n+1):\n",
    "                nums=[]\n",
    "                for i in range(1,m+1):\n",
    "                    nums.append(prefix[i][k]-prefix[i][j])\n",
    "                max_temp,left,right=self.maxSubArray(nums)\n",
    "                if max_temp>maximum:\n",
    "                    maximum=max_temp\n",
    "                    ans=[left,j,right,k-1]\n",
    "        return ans\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        sums = [[0 for j in range(n+1)] for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                sums[i][j+1] = sums[i][j] + matrix[i][j] \n",
    "        res = -float('inf')\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n+1):\n",
    "                dp = -1\n",
    "                t = 0\n",
    "                for d in range(m):\n",
    "                    num = sums[d][j] - sums[d][i]\n",
    "                    if dp > 0: dp += num\n",
    "                    else: t, dp = d, num\n",
    "                    if dp > res:\n",
    "                        res = dp\n",
    "                        ans = [t, i, d, j-1]        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        row_accu = [[0] * n for _ in range(m+1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                row_accu[i+1][j] = row_accu[i][j] + matrix[i][j]\n",
    "        ans = [0] * 4\n",
    "        max_sum = matrix[0][0]\n",
    "        curr_row_accu = [0] * n\n",
    "        for i1 in range(m):\n",
    "            slide_row_acc = [0] * n\n",
    "            for i2 in range(i1, m):\n",
    "                for j in range(n):\n",
    "                    slide_row_acc[j] = row_accu[i2+1][j] - row_accu[i1][j]\n",
    "                tmp_sum = slide_row_acc[0]\n",
    "                start = 0\n",
    "                for j in range(1, n):\n",
    "                    if tmp_sum > 0:\n",
    "                        tmp_sum += slide_row_acc[j]\n",
    "                    else:\n",
    "                        start = j\n",
    "                        tmp_sum = slide_row_acc[j]\n",
    "                    if tmp_sum > max_sum:\n",
    "                        max_sum = tmp_sum\n",
    "                        ans = [i1, start, i2, j]\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return []\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        pre_arr = [[0 for j in range(m)] for i in range( n +1)]\n",
    "        for i in range(1 , n +1):\n",
    "            for j in range(m):\n",
    "                pre_arr[i][j] = pre_arr[ i -1][j] + matrix[ i -1][j]\n",
    "\n",
    "        # print(pre_arr)\n",
    "        def getGap(i, j):\n",
    "            res = [0 for k in range(m)]\n",
    "            for t in range(m):\n",
    "                res[t] =  pre_arr[ j +1][t] - pre_arr[i][t]\n",
    "            return res\n",
    "\n",
    "        \n",
    "        data = -float('inf')\n",
    "        def getMaxOneSquire(arr):\n",
    "            m_x = -float('inf')\n",
    "            n = len(arr)\n",
    "            max_end = 0\n",
    "            begin = 0\n",
    "            max_begin = 0\n",
    "            curr_sum = -float('inf')\n",
    "            for i in range(0 , n):\n",
    "                if curr_sum < 0:\n",
    "                    curr_sum = arr[i]\n",
    "                    begin = i\n",
    "                else:\n",
    "                    curr_sum = curr_sum + arr[i]\n",
    "                if curr_sum > m_x:\n",
    "                    m_x = curr_sum\n",
    "                    max_begin = begin\n",
    "                    max_end = i\n",
    "\n",
    "            return m_x, max_begin, max_end\n",
    "\n",
    "        r1 ,r2 ,c1 ,c2 = 0 ,0 ,0 ,0\n",
    "        for j in range(n):\n",
    "            for i in range( j +1):\n",
    "                p =  getGap(i ,j)\n",
    "                t, l1, l2 = getMaxOneSquire(p)\n",
    "                if t > data:\n",
    "                    data = t\n",
    "                    c1 ,c2 = l1, l2\n",
    "                    r1 ,r2 = i, j\n",
    "        return [r1 ,c1 ,r2 ,c2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [[-inf]*m for _ in range(m)]\n",
    "        idx = [[-1]*m for _ in range(m)]\n",
    "        r = -inf\n",
    "        for i in range(n):\n",
    "            presum = [0]\n",
    "            for j in range(m): presum.append(presum[-1]+matrix[j][i])\n",
    "            for j in range(m):\n",
    "                for k in range(j, m):\n",
    "                    if dp[j][k] > 0: dp[j][k] += presum[k+1]-presum[j]\n",
    "                    else:\n",
    "                        dp[j][k] = presum[k+1]-presum[j]\n",
    "                        idx[j][k] = i\n",
    "                    if dp[j][k] > r:\n",
    "                        r = dp[j][k]\n",
    "                        ret = [j, idx[j][k], k, i]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        sums = [[0 for j in range(n+1)] for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                sums[i][j+1] = sums[i][j] + matrix[i][j] \n",
    "        res = -float('inf')\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n+1):\n",
    "                dp = -1\n",
    "                t = 0\n",
    "                for d in range(m):\n",
    "                    num = sums[d][j] - sums[d][i]\n",
    "                    if dp > 0: dp += num\n",
    "                    else: t, dp = d, num\n",
    "                    if dp > res:\n",
    "                        res = dp\n",
    "                        ans = [t, i, d, j-1]        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return []\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        pre_arr = [[0 for j in range(m)] for i in range( n +1)]\n",
    "        for i in range(1 , n +1):\n",
    "            for j in range(m):\n",
    "                pre_arr[i][j] = pre_arr[ i -1][j] + matrix[ i -1][j]\n",
    "\n",
    "        # print(pre_arr)\n",
    "        def getGap(i, j):\n",
    "            res = [0 for k in range(m)]\n",
    "            for t in range(m):\n",
    "                res[t] =  pre_arr[ j +1][t] - pre_arr[i][t]\n",
    "            return res\n",
    "\n",
    "        \n",
    "        data = -float('inf')\n",
    "        def getMaxOneSquire(arr):\n",
    "            m_x = -float('inf')\n",
    "            n = len(arr)\n",
    "            max_end = 0\n",
    "            begin = 0\n",
    "            max_begin = 0\n",
    "            curr_sum = -float('inf')\n",
    "            for i in range(0 , n):\n",
    "                if curr_sum < 0:\n",
    "                    curr_sum = arr[i]\n",
    "                    begin = i\n",
    "                else:\n",
    "                    curr_sum = curr_sum + arr[i]\n",
    "                if curr_sum > m_x:\n",
    "                    m_x = curr_sum\n",
    "                    max_begin = begin\n",
    "                    max_end = i\n",
    "\n",
    "            return m_x, max_begin, max_end\n",
    "\n",
    "        r1 ,r2 ,c1 ,c2 = 0 , 0 , 0 ,0\n",
    "        for j in range(n):\n",
    "            for i in range( j +1):\n",
    "                p =  getGap(i ,j)\n",
    "                t, l1, l2 = getMaxOneSquire(p)\n",
    "                if t > data:\n",
    "                    data = t\n",
    "                    c1 ,c2 = l1, l2\n",
    "                    r1 ,r2 = i, j\n",
    "        return [r1 ,c1 ,r2 ,c2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n = len(matrix)\n",
    "        m = len(matrix[0])\n",
    "        prematrix = [[0]*m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if i != 0:\n",
    "                    prematrix[i][j] = prematrix[i-1][j] + matrix[i][j]\n",
    "                else:\n",
    "                    prematrix[i][j] = matrix[i][j]\n",
    "        r1, r2, c1, c2 = 0,0,0,0\n",
    "        glbmax = -float('inf')\n",
    "        #print(prematrix)\n",
    "\n",
    "        for i in range(n):\n",
    "            for u in range(i + 1):\n",
    "                colsum = 0\n",
    "                left = 0\n",
    "                \n",
    "                for j in range(m):\n",
    "                    #print('i:',i,'u:',u,'j:',j)\n",
    "                    if u == 0:\n",
    "                        colsum += prematrix[i][j]\n",
    "                    else:\n",
    "                        colsum += (prematrix[i][j] - prematrix[u - 1][j])\n",
    "                    \n",
    "                    if colsum > glbmax:\n",
    "                        glbmax = colsum\n",
    "                        r1 = u\n",
    "                        r2 = left\n",
    "                        c1 = i\n",
    "                        c2 = j\n",
    "                        #print(glbmax, r1,r2,c1,c2)\n",
    "                    \n",
    "                    if colsum < 0:\n",
    "                        colsum = 0\n",
    "                        left = j + 1\n",
    "        \n",
    "        return([r1,r2,c1,c2])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        res = [-1, -1, -1, -1]\n",
    "        res_value = None\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        state = [[0] * n  for t in range(0,m+1) ]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(0,n):\n",
    "                state[i][j] = state[i-1][j] + matrix[i-1][j]\n",
    "        \n",
    "        for i in range(0,m):\n",
    "            for j in range(i+1, m+1):\n",
    "                now_state = [0] * n\n",
    "                for k in range(0,n):\n",
    "                    now_state[k] = state[j][k] - state[i][k]\n",
    "                \n",
    "                sum_state = [0] * (n+1)\n",
    "                for k in range(1,n+1):\n",
    "                    sum_state[k] = sum_state[k-1] + now_state[k-1]\n",
    "                \n",
    "                temp_min_index = 0\n",
    "                temp_min = sum_state[0]\n",
    "                for k in range(1,n+1):\n",
    "                    if res_value == None or (sum_state[k] - temp_min) > res_value:\n",
    "                        res_value = sum_state[k] - temp_min\n",
    "                        res = [i, temp_min_index, j-1, k-1]\n",
    "                    if k < n and sum_state[k] < temp_min:\n",
    "                        temp_min = sum_state[k]\n",
    "                        temp_min_index = k\n",
    "        \n",
    "        return res\n",
    "\n",
    "         \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        p_sum = [[0] * m for _ in range(n)]\n",
    "        p_sum[0][0] = matrix[0][0]\n",
    "        for j in range(1, m):\n",
    "            p_sum[0][j] = p_sum[0][j - 1] + matrix[0][j]\n",
    "        for i in range(1, n):\n",
    "            p_sum[i][0] = p_sum[i - 1][0] + matrix[i][0]\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, m):\n",
    "                p_sum[i][j] = (\n",
    "                    p_sum[i - 1][j]\n",
    "                    + p_sum[i][j - 1]\n",
    "                    - p_sum[i - 1][j - 1]\n",
    "                    + matrix[i][j]\n",
    "                )\n",
    "        max_sum = matrix[0][0]\n",
    "        r1, c1, r2, c2 = 0, 0, 0, 0\n",
    "        for i1 in range(n):\n",
    "            for i2 in range(i1, n):\n",
    "                temp_sum = 0\n",
    "                prev_c = 0\n",
    "                for j in range(m):\n",
    "                    temp_val = p_sum[i2][j]\n",
    "                    if j - 1 >= 0:\n",
    "                        temp_val -= p_sum[i2][j - 1]\n",
    "                    if i1 - 1 >= 0:\n",
    "                        temp_val -= p_sum[i1 - 1][j]\n",
    "                    if j - 1 >= 0 and i1 - 1 >= 0:\n",
    "                        temp_val += p_sum[i1 - 1][j - 1]\n",
    "                    if temp_sum < 0:\n",
    "                        temp_sum = 0\n",
    "                        prev_c = j\n",
    "                    temp_sum += temp_val\n",
    "                    if temp_sum > max_sum:\n",
    "                        max_sum = temp_sum\n",
    "                        r1, r2 = i1, i2\n",
    "                        c1, c2 = prev_c, j\n",
    "        return [r1, c1, r2, c2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return []\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        pre_arr = [[0 for j in range(m)] for i in range( n +1)]\n",
    "        for i in range(1 , n +1):\n",
    "            for j in range(m):\n",
    "                pre_arr[i][j] = pre_arr[ i -1][j] + matrix[ i -1][j]\n",
    "\n",
    "        # print(pre_arr)\n",
    "        def getGap(i, j):\n",
    "            res = [0 for k in range(m)]\n",
    "            # print(\"pre_arr[j+1]\", pre_arr[j+1], \" pre_arr[i]\", pre_arr[i])\n",
    "            for t in range(m):\n",
    "                res[t] =  pre_arr[ j +1][t] - pre_arr[i][t]\n",
    "            return res\n",
    "\n",
    "        # print(\"gap is \", getGap(1,2))\n",
    "        data = -float('inf')\n",
    "        def getMaxOneSquire(arr):\n",
    "            m_x = -float('inf')\n",
    "            if not arr:\n",
    "                return 0\n",
    "            n = len(arr)\n",
    "            #dp = [0,0]\n",
    "            max_end = 0\n",
    "            begin = 0\n",
    "            max_begin = 0\n",
    "            curr_sum = -float('inf')\n",
    "            for i in range(0 , n):\n",
    "                if curr_sum < 0:\n",
    "                    curr_sum = arr[i]\n",
    "                    begin = i\n",
    "                else:\n",
    "                    curr_sum = curr_sum + arr[i]\n",
    "                if curr_sum > m_x:\n",
    "                    m_x = curr_sum\n",
    "                    max_begin = begin\n",
    "                    max_end = i\n",
    "\n",
    "            return m_x, max_begin, max_end\n",
    "\n",
    "        r1 ,r2 ,c1 ,c2 = 0 ,0 ,0 ,0\n",
    "        for j in range(n):\n",
    "            for i in range( j +1):\n",
    "                p =  getGap(i ,j)\n",
    "                t, l1, l2 = getMaxOneSquire(p)\n",
    "                if t > data:\n",
    "                    data = t\n",
    "                    c1 ,c2 = l1, l2\n",
    "                    r1 ,r2 = i, j\n",
    "        return [r1 ,c1 ,r2 ,c2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        ans = None\n",
    "        area = -1\n",
    "        prefix_sum = []\n",
    "        s = [0] * n\n",
    "        prefix_sum.append(deepcopy(s))\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                s[j] += matrix[i][j]\n",
    "            prefix_sum.append(deepcopy(s))\n",
    "        for i in range(m):\n",
    "            for j in range(i, m):\n",
    "                arr = []\n",
    "                for k in range(n):\n",
    "                    arr.append(prefix_sum[j + 1][k] - prefix_sum[i][k])\n",
    "                dp = arr[0]\n",
    "                begin = 0\n",
    "                if area == -1 or area < dp:\n",
    "                    area = dp\n",
    "                    ans = [i, 0, j, 0]\n",
    "                for k in range(1, n):\n",
    "                    if dp < 0:\n",
    "                        begin = k\n",
    "                        dp = arr[k]\n",
    "                    else:\n",
    "                        dp = dp + arr[k]\n",
    "                    if area == -1 or area < dp:\n",
    "                        area = dp\n",
    "                        ans = [i, begin, j, k]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return []\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        pre_arr = [[0 for j in range(m)] for i in range( n +1)]\n",
    "        for i in range(1 , n +1):\n",
    "            for j in range(m):\n",
    "                pre_arr[i][j] = pre_arr[ i -1][j] + matrix[ i -1][j]\n",
    "        def getGap(i, j):\n",
    "            res = [0 for k in range(m)]\n",
    "            for t in range(m):\n",
    "                res[t] =  pre_arr[ j +1][t] - pre_arr[i][t]\n",
    "            return res\n",
    "\n",
    "        \n",
    "        data = -float('inf')\n",
    "        def getMaxOneSquire(arr):\n",
    "            m_x = -float('inf')\n",
    "            n = len(arr)\n",
    "            max_end = 0\n",
    "            begin = 0\n",
    "            max_begin = 0\n",
    "            curr_sum = -float('inf')\n",
    "            for i in range(0 , n):\n",
    "                if curr_sum < 0:\n",
    "                    curr_sum = arr[i]\n",
    "                    begin = i\n",
    "                else:\n",
    "                    curr_sum = curr_sum + arr[i]\n",
    "                if curr_sum > m_x:\n",
    "                    m_x = curr_sum\n",
    "                    max_begin = begin\n",
    "                    max_end = i\n",
    "\n",
    "            return m_x, max_begin, max_end\n",
    "\n",
    "        r1 ,r2 ,c1 ,c2 = 0 , 0 , 0 ,0\n",
    "        for j in range(n):\n",
    "            for i in range( j +1):\n",
    "                p =  getGap(i ,j)\n",
    "                t, l1, l2 = getMaxOneSquire(p)\n",
    "                if t > data:\n",
    "                    data = t\n",
    "                    c1 ,c2 = l1, l2\n",
    "                    r1 ,r2 = i, j\n",
    "        return [r1 ,c1 ,r2 ,c2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n = len(matrix)    # 行数\n",
    "        if n == 0:\n",
    "            return []\n",
    "        m = len(matrix[0])    # 列数\n",
    "        # 计算二维前缀和，pre[i][j] 表示s[:i][:j]的前缀和\n",
    "        pre = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                pre[i + 1][j + 1] = pre[i][j + 1] + pre[i + 1][j] + matrix[i][j] - pre[i][j]\n",
    "        \n",
    "        ans = -inf\n",
    "        p = [0, 0, 0, 0]\n",
    "        for top in range(n):  # 假设最优子矩阵是在top,left为左上角，bottom, right为右下角\n",
    "            for bottom in range(top, n):\n",
    "                left = 0\n",
    "                cur = 0    # 记录当前子矩阵的最大值\n",
    "                for right in range(m):\n",
    "                    localmax = pre[bottom + 1][right + 1] - pre[bottom + 1][left] - pre[top][right + 1] + pre[top][left]\n",
    "                    if localmax > ans:\n",
    "                        p = [top, left, bottom, right]\n",
    "                        ans = localmax\n",
    "                    if localmax < 0:   # 从下移列开始\n",
    "                        localmax = 0\n",
    "                        left = right + 1\n",
    "        return p\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        presum = [[0]*(m+1) for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, m+1):\n",
    "                presum[i][j] = matrix[i-1][j-1] +presum[i-1][j]+presum[i][j-1]-presum[i-1][j-1]\n",
    "        \n",
    "        res = [0,0,0,0]\n",
    "        tmpmax = float('-inf')\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                l = 0\n",
    "                for r in range(m):\n",
    "                    thismax = presum[j+1][r+1]-presum[i][r+1]-presum[j+1][l]+presum[i][l]\n",
    "                    if thismax>tmpmax:\n",
    "                        tmpmax = thismax\n",
    "                        res[0], res[1], res[2], res[3] = i, l, j, r\n",
    "                    if thismax < 0:\n",
    "                        thismax = 0\n",
    "                        l = r+1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        pre_s = [[0] * n for _ in range(m+1)]\n",
    "        for c in range(n):\n",
    "            for r in range(1, m+1):\n",
    "                pre_s[r][c] = pre_s[r-1][c] + matrix[r-1][c]\n",
    "\n",
    "        max_s = -inf\n",
    "        r1 = c1 = r2 = c2 = -1\n",
    "        for i in range(m):\n",
    "            for j in range(i, m):\n",
    "                b = [pre_s[j+1][c] - pre_s[i][c] for c in range(n)]\n",
    "                f = [-inf for _ in range(n+1)]\n",
    "                begin = 0\n",
    "                for k, x in enumerate(b):\n",
    "                    if f[k] > 0:\n",
    "                        f[k+1] = f[k] + x\n",
    "                    else:\n",
    "                        f[k+1] = x\n",
    "                        begin = k\n",
    "                    if f[k+1] > max_s:\n",
    "                        max_s = f[k+1]\n",
    "                        r1 = i\n",
    "                        r2 = j\n",
    "                        c1 = begin\n",
    "                        c2 = k\n",
    "        return [r1, c1, r2, c2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        s = [[0] * (n + 1) for i in range(m + 1)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + matrix[i][j]\n",
    "\n",
    "        def query(x2, y2, x1, y1):\n",
    "            return s[x2][y2] - s[x2][y1] - s[x1][y2] + s[x1][y1]\n",
    "        \n",
    "        ans = []\n",
    "        ans_val = -inf\n",
    "        for i in range(m):\n",
    "            for j in range(i, m):\n",
    "                pre_val = 0\n",
    "                pre_index = 0\n",
    "                for k in range(n):\n",
    "                    if pre_val < 0:\n",
    "                        pre_index = k\n",
    "                    cur = query(j + 1, k + 1, i, pre_index)\n",
    "                    if cur > ans_val:\n",
    "                        ans_val = cur\n",
    "                        ans = [i, pre_index, j, k]\n",
    "                    pre_val = cur\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n = len(matrix)\n",
    "        m = len(matrix[0])\n",
    "\n",
    "        # 前缀和\n",
    "        prefix_sum = [[0]*(m+1) for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, m+1):\n",
    "                prefix_sum[i][j] =  prefix_sum[i-1][j] + prefix_sum[i][j-1] - prefix_sum[i-1][j-1] + matrix[i-1][j-1]\n",
    "        # print(prefix_sum)\n",
    "\n",
    "        globalmax = float('-inf')\n",
    "        ans = [0]*4\n",
    "        for top in range(n):\n",
    "            for bottom in range(top, n):\n",
    "                localmax, left = 0, 0\n",
    "                for right in range(m):\n",
    "                    # 利用presum快速求出localMax\n",
    "                    # localmax = prefix_sum[bottom+1][right+1]+prefix_sum[top+1][left+1]-prefix_sum[bottom+1][left+1]-prefix_sum[top+1][right+1]\n",
    "                    localmax = prefix_sum[bottom + 1][right + 1] + prefix_sum[top][left] - prefix_sum[bottom + 1][left] - prefix_sum[top][right + 1];\n",
    "                    if globalmax < localmax:\n",
    "                        globalmax = localmax\n",
    "                        ans[0] = top\n",
    "                        ans[1] = left\n",
    "                        ans[2] = bottom\n",
    "                        ans[3] = right\n",
    "                    if localmax < 0:\n",
    "                        localmax = 0\n",
    "                        left = right + 1\n",
    "        return ans\n",
    "                    \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        sums = [[0] * (n + 1) for i in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                sums[i+1][j+1] = sums[i][j+1] + sums[i+1][j] - sums[i][j] + matrix[i][j]\n",
    "        \n",
    "        maxSum = -100000\n",
    "        for bot in range(m):\n",
    "            for top in range(bot, m):\n",
    "                dp = [0, 0]\n",
    "                for col in range(n):\n",
    "                    tmp = sums[top+1][col+1] - sums[top+1][col] - sums[bot][col+1] + sums[bot][col]\n",
    "                    if dp[col % 2] > 0:\n",
    "                        dp[(col+1) % 2] = dp[col % 2] + tmp\n",
    "                    else:\n",
    "                        dp[(col+1) % 2] = tmp\n",
    "                        begin = bot, col\n",
    "                    if dp[(col+1) % 2] > maxSum:\n",
    "                        maxSum = dp[(col+1) % 2]\n",
    "                        result = *begin, top, col\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        M,N = len(matrix),len(matrix[0])\n",
    "        pre = [[0]*N for i in range(M)]\n",
    "        for i in range(M):\n",
    "            for j in range(N):\n",
    "                t = pre[i-1][j] if i>0 else 0 \n",
    "                l = pre[i][j-1] if j>0 else 0 \n",
    "                ins = pre[i-1][j-1] if i>0 and j>0 else 0 \n",
    "                pre[i][j] = matrix[i][j]+l+t-ins\n",
    "        maxS = matrix[0][0]\n",
    "        ret = [0,0,0,0]\n",
    "        # print(pre)\n",
    "        for r in range(N):\n",
    "            for l in range(r+1):\n",
    "                minT = 0\n",
    "                idxT = -1\n",
    "                for t in range(M):\n",
    "                    cur = pre[t][r] - (pre[t][l-1] if l>0 else 0)\n",
    "                    if maxS<cur-minT:\n",
    "                        maxS = cur-minT\n",
    "                        ret = [idxT+1,l,t,r]\n",
    "                        # print(ret,matrix[idxT+1:t+1][l:r+1],maxS,l,r,t)\n",
    "                    if minT>cur:\n",
    "                        minT = cur \n",
    "                        idxT = t \n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        cum_states = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                cum_states[i][j] = matrix[i][j] + cum_states[i][j + 1] + cum_states[i + 1][j] - cum_states[i + 1][j + 1]\n",
    "\n",
    "        max_sum = -math.inf\n",
    "        res = None\n",
    "        for i1 in range(m):\n",
    "            for i2 in range(i1, m):\n",
    "                col_sum = [cum_states[i1][j] - cum_states[i2+1][j] for j in range(n)]\n",
    "\n",
    "                row_min_sum = 0\n",
    "                row_min_col = n-1\n",
    "                for j in range(n-1, -1, -1):\n",
    "                    if col_sum[j] - row_min_sum > max_sum:\n",
    "                        max_sum = col_sum[j] - row_min_sum\n",
    "                        res = [i1, j, i2, row_min_col]\n",
    "\n",
    "                    if col_sum[j] < row_min_sum:\n",
    "                        row_min_sum = col_sum[j]\n",
    "                        row_min_col = j - 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix):\n",
    "        m,n = len(matrix), len(matrix[0])\n",
    "        sum_arr = [[0 for j in range(n)] for i in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                sum_arr[i][j] = matrix[i][j]\n",
    "                if i-1 >= 0:\n",
    "                    sum_arr[i][j] += sum_arr[i-1][j]\n",
    "                if j-1 >= 0:\n",
    "                    sum_arr[i][j] += sum_arr[i][j-1]\n",
    "                if i-1 >= 0 and j-1 >=0:\n",
    "                    sum_arr[i][j] -= sum_arr[i-1][j-1]\n",
    "        \n",
    "        def cal_area(x1, y1, x2, y2):\n",
    "            area = sum_arr[x2][y2]\n",
    "            if x1-1 >= 0:\n",
    "                area -= sum_arr[x1-1][y2]\n",
    "            if y1-1 >= 0 :\n",
    "                area -= sum_arr[x2][y1-1]\n",
    "            if x1-1 >= 0 and y1-1 >= 0:\n",
    "                area += sum_arr[x1-1][y1-1]\n",
    "            return area\n",
    "        \n",
    "        def dp(nums: list):\n",
    "            dp_i = nums[0]\n",
    "            begin = 0\n",
    "            ret = [0,0,dp_i]\n",
    "\n",
    "            for i in range(1, len(nums)):\n",
    "                val = nums[i]\n",
    "                if dp_i > 0:\n",
    "                    dp_i += val\n",
    "                else:\n",
    "                    dp_i = val\n",
    "                    begin = i\n",
    "                if dp_i > ret[2]:\n",
    "                    ret[2] = dp_i\n",
    "                    ret[0] = begin\n",
    "                    ret[1] = i\n",
    "            return ret\n",
    "\n",
    "        max_area = -1000000000000\n",
    "        ans = []\n",
    "        for x1 in range(m):\n",
    "            for x2 in range(x1,m):\n",
    "                y1,y2,area = dp([cal_area(x1, j, x2, j) for j in range(n)])\n",
    "                if area > max_area:\n",
    "                    max_area =area\n",
    "                    ans = [x1, y1, x2, y2]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums):\n",
    "        n = len(nums)\n",
    "        dp = [[0,0,0] for _ in range(n)]\n",
    "        dp[0][0] = nums[0]\n",
    "        res = dp[0][0]\n",
    "        l = 0\n",
    "        r = 0\n",
    "        for i in range(1, n):\n",
    "            if dp[i-1][0] + nums[i] < nums[i]:\n",
    "                dp[i] = [nums[i], i, i]\n",
    "            else:\n",
    "                dp[i][0] = dp[i-1][0] + nums[i]\n",
    "                dp[i][1] = dp[i-1][1]\n",
    "                dp[i][2] = i\n",
    "            if dp[i][0] > res:\n",
    "                res = dp[i][0]\n",
    "                l = dp[i][1]\n",
    "                r = dp[i][2]\n",
    "        return res, l, r\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        ans = matrix[0][0]\n",
    "        pos = [0,0,0,0]\n",
    "        pre_sum = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                pre_sum[i][j] = pre_sum[i-1][j] + pre_sum[i][j-1] - pre_sum[i-1][j-1] + matrix[i-1][j-1]\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(i, m+1):\n",
    "                dp = [0]*n\n",
    "                for k in range(1, n+1):\n",
    "                    dp[k-1] = pre_sum[j][k] - pre_sum[i-1][k] - pre_sum[j][k-1] + pre_sum[i-1][k-1]\n",
    "                tmp, l, r = self.maxSubArray(dp)\n",
    "                if tmp > ans:\n",
    "                    ans = tmp\n",
    "                    pos = [i-1, l, j-1, r]\n",
    "        return pos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from cmath import inf\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        n=len(matrix)\n",
    "        m=len(matrix[0])\n",
    "        pre=[[0]*(m+1)for _ in range(n+1)]\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,m+1):\n",
    "                pre[i][j]=matrix[i-1][j-1]+pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]\n",
    "        ans=-inf\n",
    "        res=[0]*4\n",
    "        for top in range(n):\n",
    "            for bottom in range(top,n):\n",
    "                left=0\n",
    "                for right in range(m):\n",
    "                    l=pre[bottom+1][right+1]-pre[bottom+1][left]-pre[top][right+1]+pre[top][left]\n",
    "                    if l>ans:\n",
    "                        ans=l\n",
    "                        res=[top,left,bottom,right]\n",
    "                    if l<0:\n",
    "                        left=right+1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        row, col = len(matrix), len(matrix[0])\n",
    "        # 2D to 1D\n",
    "        for i in range(row):\n",
    "            for j in range(1, col):\n",
    "                matrix[i][j] += matrix[i][j - 1]\n",
    "        max_sum = matrix[0][0]\n",
    "        r1, c1, r2, c2 = 0, 0, 0, 0\n",
    "        ans = [r1, c1, r2, c2]\n",
    "        for i in range(col):\n",
    "            for j in range(i, col):\n",
    "                cur = 0\n",
    "                for k in range(row):\n",
    "                    pre = matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0)\n",
    "                    if cur > 0:\n",
    "                        cur += pre\n",
    "                    else:\n",
    "                        cur = pre\n",
    "                        r1, c1 = k, i\n",
    "                    if cur > max_sum:\n",
    "                        max_sum = cur\n",
    "                        r2, c2 = k, j\n",
    "                        ans = [r1, c1, r2, c2]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        sums = [[0] * (n + 1) for i in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                sums[i+1][j+1] = sums[i][j+1] + sums[i+1][j] - sums[i][j] + matrix[i][j]\n",
    "        \n",
    "        maxSum = -100000\n",
    "        for bot in range(m):\n",
    "            for top in range(bot, m):\n",
    "                dp = [(0, (bot, 0))]\n",
    "                for col in range(n):\n",
    "                    tmp = sums[top+1][col+1] - sums[top+1][col] - sums[bot][col+1] + sums[bot][col]\n",
    "                    if dp[col][0] > 0:\n",
    "                        dp.append((dp[col][0] + tmp, dp[col][1]))\n",
    "                    else:\n",
    "                        dp.append((tmp, (bot, col)))\n",
    "                    if dp[col+1][0] > maxSum:\n",
    "                        maxSum = dp[col+1][0]\n",
    "                        result = *dp[col+1][1], top, col\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        s1, s2 = len(matrix), len(matrix[0])\n",
    "\n",
    "        # 计算前缀和矩阵\n",
    "        # O(N×M)\n",
    "        T1 = [[0] * (s2 + 1) for _ in range(s1)]  # 左上缀和\n",
    "\n",
    "        T1[0][1] = matrix[0][0]\n",
    "\n",
    "        for i1 in range(1, s1):\n",
    "            T1[i1][1] = T1[i1 - 1][1] + matrix[i1][0]\n",
    "\n",
    "        for i2 in range(1, s2):\n",
    "            T1[0][i2 + 1] = T1[0][i2] + matrix[0][i2]\n",
    "\n",
    "        for i1 in range(1, s1):\n",
    "            for i2 in range(1, s2):\n",
    "                T1[i1][i2 + 1] = matrix[i1][i2] + T1[i1 - 1][i2 + 1] + T1[i1][i2] - T1[i1 - 1][i2]\n",
    "\n",
    "        ans_idx, ans_val = [-1, -1, -1, -1], float(\"-inf\")\n",
    "\n",
    "        # 计算前缀差矩阵\n",
    "        # O(N×M^2)\n",
    "        T2 = [[(0, -1)] * (s2 + 1) for _ in range(s2 + 1)]  # 左上缀差\n",
    "        for i1 in range(s1):\n",
    "            for i2 in range(s2):\n",
    "                for i3 in range(i2, s2):\n",
    "                    v1 = T1[i1][i3 + 1] - T1[i1][i2]\n",
    "                    v2 = v1 - T2[i2][i3][0]\n",
    "\n",
    "                    # print(i1, i2, i3, \"->\", v2, \":\", (T2[i2][i3][1] + 1, i2), \",\", (i1, i3), \"(\", T2[i2][i3], \")\")\n",
    "\n",
    "                    if v2 > ans_val:\n",
    "                        ans_idx, ans_val = [T2[i2][i3][1] + 1, i2, i1, i3], v2\n",
    "                        # print(\"[Maybe]\", ans_idx, ans_val)\n",
    "\n",
    "                    if v1 < T2[i2][i3][0]:\n",
    "                        T2[i2][i3] = (v1, i1)\n",
    "\n",
    "                    # T2[i2][i3] = min(T2[i2][i3], v)\n",
    "\n",
    "        return ans_idx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class VirtualArray(object):\n",
    "\n",
    "    def __init__(self, matrix, row1, row2):\n",
    "        self.len = len(matrix[0])\n",
    "        self.matrix = matrix\n",
    "        self.row1 = row1\n",
    "        self.row2 = row2\n",
    "\n",
    "    def __len__(self):\n",
    "        return self.len\n",
    "\n",
    "    def __getitem__(self, item):\n",
    "        if self.row1 > 0:\n",
    "            return self.matrix[self.row2][item] - self.matrix[self.row1 - 1][item]\n",
    "        else:\n",
    "            return self.matrix[self.row2][item]\n",
    "\n",
    "    def to_list(self):\n",
    "        return [self[i] for i in range(len(self))]\n",
    "\n",
    "    def __repr__(self):\n",
    "        return str(self.to_list())\n",
    "\n",
    "\n",
    "def find_max_sub_seq(arr):\n",
    "    n = len(arr)\n",
    "    max_sum = float(\"-inf\")\n",
    "    max_idx = None\n",
    "    prev_sum = 0\n",
    "    prev_idx = None\n",
    "    for i in range(n):\n",
    "        v = arr[i]\n",
    "        if prev_idx is None or prev_sum <= 0:\n",
    "            curr_sum = v\n",
    "            curr_idx = (i, i)\n",
    "        else:\n",
    "            curr_sum = prev_sum + v\n",
    "            curr_idx = (prev_idx[0], i)\n",
    "\n",
    "        if curr_sum > max_sum or prev_idx is None:\n",
    "            max_sum = curr_sum\n",
    "            max_idx = curr_idx\n",
    "        else:\n",
    "            pass\n",
    "\n",
    "        prev_sum = curr_sum\n",
    "        prev_idx = curr_idx\n",
    "\n",
    "    return max_sum, max_idx\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        for col in range(n):\n",
    "            for row in range(m):\n",
    "                matrix[row][col] += (matrix[row - 1][col] if row > 0 else 0)\n",
    "\n",
    "        max_sum = float(\"-inf\")\n",
    "        max_idx = None\n",
    "        for row1 in range(m):\n",
    "            for row2 in range(row1, m):\n",
    "                arr = VirtualArray(matrix, row1, row2)\n",
    "                seq_sum, seq_idx = find_max_sub_seq(arr)\n",
    "                if max_idx is None or max_sum <= seq_sum:\n",
    "                    max_sum = seq_sum\n",
    "                    max_idx = (row1, seq_idx[0], row2, seq_idx[1])\n",
    "        \n",
    "        return max_idx\n",
    "    \n",
    "    \n",
    "if __name__ == '__main__':\n",
    "#     m = [\n",
    "#         [9,-8,1,3,-2],\n",
    "#         [-3,7,6,-2,4],\n",
    "#         [6,-4,-4,8,-7]\n",
    "#     ]\n",
    "    m = [[450, 309, 460, -155, 337, -335, 45, -220, -209, 352, -348, -448, 412, 37, 155, -283, 493, -500, -116, -260, -443, 40, -235, 400, 468, 400, 446, 186, -84, 196, -363, -252, -193, -110, -26, -124, 116, -210, -374, -69, 142, 137, 316, 136, -73, 393, 388, -188, 37, 41, 286, -93, -107, 80, -125, -486, 119, 197, -333, 409], [376, 369, -16, -364, 183, 427, 161, -115, 173, 117, -494, 21, 59, 286, -470, 377, -291, 200, 162, -344, -430, 313, 246, -255, -48, 357, 112, -98, 393, -460, -335, -79, -413, -281, -380, 315, 367, -446, 87, -77, 351, -165, -495, -338, -341, 196, 445, 431, 119, 331, 121, 118, -355, -381, -350, -127, 394, -339, 264, -247], [-263, -117, 67, 207, 344, 404, -338, 311, -313, 411, 285, 70, 193, -185, 434, 459, 363, -458, -73, -235, 261, -403, -332, -405, -498, -283, 393, -122, 143, 226, 147, -316, 147, -308, -111, -36, 474, -317, 214, -423, -119, 245, 314, -80, 83, 61, -376, 475, -477, 354, 258, -416, 476, -262, -110, 399, 102, 333, -54, 334], [-86, -221, 209, 266, 9, -366, 151, 248, -63, -108, -250, -469, 492, 142, -159, -66, 291, -73, 392, 405, -60, -500, 453, 483, -444, 326, 192, -361, -266, -389, -136, 448, -278, 172, 154, 373, 93, -297, 122, -263, 96, -228, 481, 236, -121, -498, -426, 207, -394, 247, -388, -241, -3, -200, -359, -453, -271, -350, -127, -86], [-204, 448, 451, -483, -477, -62, 355, -267, -470, -334, 431, -92, 333, -339, -357, -398, 135, -113, -99, -221, 361, -423, -166, -284, -163, -358, 249, 391, 499, -14, 333, -40, 338, 263, -260, 170, -495, 276, 84, 244, 230, 342, 117, 392, -411, -404, -200, 485, -331, 232, 344, 390, -363, -372, -214, -91, 366, -21, -333, 100], [178, 10, 182, 462, -467, 226, -303, -149, 350, -449, -422, 80, -251, -434, -72, -159, -105, -251, -29, 123, 223, 67, 220, 18, 331, 193, -457, 25, 149, -319, -483, 72, -28, 266, -1, -318, 362, 284, 137, 435, -308, 143, 404, 423, 202, 58, 65, -342, -385, -385, 12, -111, 112, 403, -448, 13, -280, 366, 14, -256], [-436, -412, -356, 100, -359, -289, -231, -134, 355, -9, 218, 483, -296, -50, 361, -433, -117, -428, -135, -398, -315, -261, -368, -474, -339, 320, -128, 411, -423, 226, -115, -450, 201, -290, -113, 382, 394, 9, 462, 200, -101, 484, 402, -26, 165, 121, -115, 160, -166, -297, 9, -347, -381, -349, -175, 19, -290, 126, -308, -38], [394, 78, -379, 140, -284, 275, 156, 309, -407, 239, -64, -298, -320, -256, -256, -433, -60, -458, -236, -386, -263, 395, -390, 343, 417, -396, -95, 161, -242, 355, 483, 299, -459, -257, 312, 196, 384, 315, 48, -177, -3, -473, -41, -173, -127, -252, -479, -488, 212, -460, 236, 19, 305, 320, 437, 280, 318, 256, 185, -122], [-283, 154, -49, -383, -57, 164, 57, 358, -479, 496, -271, -85, 6, -496, 380, -398, 100, -491, -321, 231, 18, 13, -341, 335, -356, -83, 360, 69, 72, -288, 374, 159, -370, 118, 162, -454, 117, 74, 346, 110, 474, -127, -315, 311, -414, -57, 62, -55, -237, -187, -427, -356, -129, -229, 299, -243, 474, 413, -402, 42], [380, 390, -398, -468, -272, 92, 440, 25, -240, -232, 47, -494, 153, 203, 70, -223, 460, -5, 177, 123, -471, -235, -321, -471, -92, -447, -449, -341, 153, 276, 64, 145, -103, 6, -331, -336, -210, 301, 402, -150, -437, -130, 236, -65, 169, -484, -87, 314, 262, 414, -222, -128, 112, 77, 155, 305, 160, -362, -400, 129], [-134, -187, 288, 345, 274, 23, -54, -235, -191, 294, -123, 247, 150, -38, -169, 55, -252, 27, -365, -397, 438, 190, -7, -216, 57, -336, -335, 308, -481, -452, -31, 83, -172, 299, 442, -302, 43, 350, -275, 46, 294, 293, 282, 51, -361, -363, -202, -65, 92, -133, 271, -232, -439, 447, 83, -256, -274, -222, -324, -411], [-481, -454, 30, 328, -366, -453, 435, 383, -428, -163, 420, 352, -403, -253, -82, 245, 496, 151, -337, -435, -362, 354, 2, 45, -428, -487, 211, -262, -485, 346, 364, -435, 295, -318, 286, 25, -414, 28, -3, 439, -98, 55, -296, 397, -87, -47, 494, 311, 350, -178, 472, -289, 38, -318, -429, -80, -20, -338, -95, -412], [479, -297, -83, -369, -220, 469, 408, -215, 122, -433, 239, 17, -463, 342, -100, -333, -57, -405, -86, 39, -54, -289, -220, -221, -66, 347, -269, -362, 299, 398, 257, 427, 436, 284, -13, 101, 289, 115, -342, 140, -16, 292, -340, 174, 478, 312, 65, 278, 485, -339, -99, 401, 198, -411, 226, 463, 368, 419, 114, -426], [-76, -102, -17, 88, 75, 424, 490, -212, -191, -327, 249, -72, -173, -139, -336, -106, -145, 422, 346, -387, -253, -31, -224, -430, 47, -420, -228, -141, 178, 61, 92, 459, 431, 269, 106, -452, -83, -305, -500, 206, -312, -44, 94, 85, 403, -438, 19, 444, -457, -48, -354, -477, -498, 349, 163, 157, -101, 28, -460, 21], [138, -469, -202, -326, -111, 329, -402, 203, -497, -374, -397, 371, -358, -426, 144, -239, 438, -298, -98, -187, 391, -476, -494, 436, 390, -339, 163, 194, -63, 373, 141, 246, 36, 92, 191, 215, -414, -238, 333, 495, -178, 26, -348, 241, -189, -319, -418, -476, 456, 194, 60, -407, 120, -310, 146, -369, 6, 81, -2, 395], [180, -468, 363, 314, -34, 481, 71, -491, 118, 379, -390, 148, 25, 385, -322, -281, -20, 184, -298, 34, 345, -182, -498, 302, -31, 188, -254, -461, 24, -496, -301, 323, -324, 324, -243, 104, -224, -74, 52, -35, -445, 108, 189, 167, -149, -429, -313, -416, -61, 361, 342, 392, 343, -102, -330, 325, 280, 412, 126, -49], [367, -41, -206, -255, -344, 423, -293, 365, 95, 156, -467, 459, -91, 491, 117, 420, 181, 352, -171, 222, 207, 347, 444, -124, -157, -360, -357, 106, 407, -185, 150, 113, -159, -439, -293, 105, 293, -35, -200, -414, -415, 231, -74, 310, 116, -428, 257, 183, 202, -433, 313, 197, 23, 468, -270, 425, 133, 254, 252, -358], [-188, 495, 361, -432, 12, -334, -198, 92, -452, 300, -104, 274, 94, 152, -120, 225, -260, -146, -243, -335, -287, -412, -116, -204, 468, -58, 100, -76, 219, 19, -398, 493, 163, -261, 429, -102, 24, 210, 200, 439, -197, -83, 335, 353, -447, 289, 50, 295, -299, 81, 412, 455, -167, 279, 315, 54, 237, 353, 496, -349], [331, -434, -434, 196, 370, 84, -410, -500, -216, 229, 401, 196, 475, 448, 228, 3, -312, 173, -24, -137, -150, -97, -4, 168, 3, -256, -467, -9, 465, 116, -40, 347, -126, 403, 198, 113, 277, -104, -172, 436, -103, 212, 358, -115, 123, 168, -37, 8, 2, -305, -81, -291, 473, -52, 145, 135, 11, -121, 235, -200], [56, 406, -98, 175, 49, 112, -382, -71, 433, -247, -417, 254, -370, -418, -464, -122, -324, 491, 238, 222, 284, -441, -46, 76, -13, 87, -444, -23, -427, 67, -50, -416, 160, 360, -280, -307, 198, 287, 229, -198, 471, 135, 492, 370, 387, 457, -269, -45, 403, -323, -320, 421, -237, -347, 193, 119, -190, 295, -53, 47], [218, -136, -416, -429, 432, 236, 122, -93, -430, 106, -138, 182, -144, -397, 172, -473, -471, 297, -162, 114, -87, 12, -460, -185, -363, 464, -68, 44, 186, -467, 411, 464, -371, 48, -321, -355, 350, 87, 53, -339, -90, 352, 114, -306, -278, -429, -437, -195, 98, -39, -130, -498, 258, -281, -411, -56, 378, 478, 291, -9], [-360, -301, 45, -319, -216, 441, -56, -239, -293, -209, -153, 339, 269, -28, -14, 44, -273, 274, -368, 249, 6, 414, 207, 454, 113, -118, -432, 264, -403, -95, -240, -329, -239, 3, 66, 101, -437, -109, 416, -146, -267, -348, 443, 136, -326, 96, -139, 279, 265, -340, 50, -221, -98, 419, -281, -423, -230, 219, 157, 55], [-199, 50, 156, 420, 444, -150, -139, 133, -487, 467, 287, -478, 241, -409, -257, -121, -430, -392, -330, 253, -376, -386, 385, 52, 78, 142, -83, -439, -41, -193, -293, -297, -434, -201, -302, -109, 333, 303, 19, 396, 469, -384, -413, 62, -186, -235, -491, -447, 149, -206, 18, 178, 48, 365, -68, -172, 228, 141, 326, -127], [31, 52, 128, -79, 113, -140, 400, 89, -177, -56, 480, 273, -372, -330, -342, -135, -5, -444, -1, -35, 235, -340, -198, -178, 46, 441, -52, 265, 227, 450, -40, -29, 41, -12, -230, 372, -150, -227, 244, 277, 340, 149, 427, -258, 438, -398, 133, 144, 131, 262, -340, 136, -329, 435, -14, 201, -71, 233, -481, 332], [31, -55, -268, 345, -284, -261, -73, -472, -347, 156, 8, -332, -194, -380, -413, -392, 373, 496, 149, 225, 492, -420, -419, 340, -48, -95, -398, 176, -224, -457, -487, 482, -17, 342, 307, 383, -15, 424, -329, 90, -115, 9, 127, -469, 415, -57, 347, 135, 378, -299, -136, -311, -346, 176, -3, -432, 88, 55, -110, -13], [159, 205, -367, 42, 317, -383, -316, 4, 245, -485, -13, -450, 359, 312, 21, 496, -25, -466, 344, 312, 67, -396, 51, 310, -248, -148, 339, -223, -435, -160, 413, -306, -4, 84, -8, -266, -242, 440, 135, -184, 390, 191, -373, 88, 207, -4, -227, 177, 137, 201, 483, 74, 138, 374, -336, 374, 125, 145, -230, 471], [-345, 399, -404, 342, 82, -40, 120, 494, 374, 15, 302, -38, -41, -482, -36, 109, 115, -396, -424, -224, -313, -149, -354, -497, -278, 13, -227, -269, -156, -275, -330, 13, -414, 242, 247, 452, 338, 275, -22, 52, 125, 423, -481, 16, -47, -206, 345, 168, 137, 45, 137, 479, 160, -63, 0, 363, 343, -101, -403, 363], [-159, -33, 458, 368, -274, -105, -285, 349, -250, -132, -22, 321, 40, 177, 267, 424, -479, -202, 298, 107, 1, 416, 396, 134, -345, 78, -306, 391, -178, 8, -315, 311, 475, 151, -377, -212, -188, -61, 21, 408, -439, 232, -197, 125, 207, -403, 452, -207, 327, 256, 195, 284, 243, 473, 172, 79, -219, 334, 97, -238], [212, 222, 492, 114, -44, 117, 43, 351, -272, 422, -477, -204, 222, 324, 13, 257, 315, 153, -414, 15, -123, -338, 261, 431, 168, 21, -471, -183, -486, -366, -78, 72, -263, -205, -188, 181, -470, 192, -459, -182, 496, 290, 66, -403, -116, -202, 449, -494, 271, 177, -175, 213, 439, 496, -418, -164, 313, -121, -135, -357], [486, -438, 187, -168, 356, 94, -481, -337, -130, 44, -494, 73, 293, 44, -86, -479, 273, 378, -154, 125, -32, -252, -373, 400, 46, 354, -482, 355, -429, 303, 487, -64, 191, 489, 332, -57, 23, 412, -315, -38, 417, -387, 101, -298, -128, 260, -252, 224, 466, -434, -85, -462, -348, 302, -296, -66, 358, -336, -64, -200], [-319, 469, 114, -229, -334, -5, 425, -494, 159, 309, -217, 94, 429, 191, 145, -468, 328, -228, 334, -132, 293, 355, -362, 394, -7, -32, -358, -64, -168, 94, 411, 203, -467, -229, -315, -116, 131, 431, 322, 485, 459, -77, 353, -406, 260, 222, -324, 184, 482, -487, -139, 164, 266, 435, -453, -235, -132, -498, -442, -24], [-464, 280, 81, 22, 285, -175, -34, 379, 60, 240, -67, -117, -204, 200, -230, -268, 284, 286, -242, -229, -330, 371, -93, -466, 373, -387, -211, -229, 345, -391, -218, -390, -170, 405, 171, -256, 67, -26, 455, 289, -222, -456, -218, -474, 296, 99, 56, -409, -308, -170, -456, -478, -401, 270, -489, 47, -142, -243, -129, -142], [426, 318, 128, -108, -165, 84, 69, -218, -235, 457, 430, -454, -10, -369, -208, 202, -247, 257, -432, 368, -170, -13, -439, -85, -279, 221, 65, -203, -477, 389, 182, -357, -302, 6, 99, -411, 341, 236, 174, -213, -371, 150, 314, 314, -232, -494, -114, -461, -387, 409, -43, -381, 466, 62, -270, -399, -75, 322, -344, -155], [101, -355, -166, 470, -29, 168, 140, 134, -100, -109, 132, -91, 19, 395, 432, -290, -288, -487, 3, -115, -377, -51, 265, 336, 95, -207, -120, 221, -305, 196, 116, 256, 492, 254, 152, -259, -412, 354, -378, 177, 364, -239, -397, 411, 166, -71, -222, -146, -140, 361, 143, 204, 141, 52, -451, -435, -359, 458, -217, -276], [-56, -54, -378, 359, 274, 244, 10, 272, -157, 383, 220, -209, 419, -449, 195, 325, 474, 303, 269, 360, -100, 233, -221, 288, -255, 189, 59, 282, 14, -1, -403, 80, 117, 395, -485, 148, -34, -28, -291, 148, -183, 105, 121, 327, -298, -95, -135, -132, 152, 406, 406, 73, -412, -264, -53, -320, 395, 231, -298, -284], [-402, -125, -252, -56, -387, -199, -23, 305, -93, 249, -238, 362, -249, 109, 407, 424, -182, 489, -252, -338, -282, -357, -275, 1, 319, -435, 446, 206, -68, 308, -229, -372, 214, -82, 261, -339, 326, -229, -371, -406, 401, -54, 459, 185, -101, -234, 300, -173, 11, 462, -261, 146, 167, 245, 53, -230, -438, 474, 442, 222], [277, -193, 403, 485, 173, -199, 438, -264, -188, 14, 97, -384, 418, 265, 278, 440, 78, -384, 397, -425, 421, -202, 26, 493, -392, 220, 258, 65, 164, 431, 293, -295, 286, 381, -236, 236, 440, -424, 4, 352, -249, 47, -256, 7, -429, 258, 258, -109, 428, 149, 240, -300, 60, 345, 406, -130, 418, -353, -361, 180], [-409, -259, -254, 212, 245, 84, 102, -439, 376, -142, 136, 215, -267, 445, 275, 253, 158, 56, 382, -437, -98, 28, 295, -480, 49, 187, -157, -88, -106, 383, -384, -369, 226, 444, 248, 12, -269, 465, -296, -355, 225, -453, 345, 464, 332, 258, 272, -402, -123, 206, 488, 383, 287, -108, -20, -98, -283, -499, -377, 283], [-82, 137, 424, -353, 352, 342, -148, -387, -497, 426, -310, 477, 368, 307, 367, 139, -290, -459, -381, -261, -386, 139, -70, 353, -331, -70, 412, 397, 297, 278, 366, -327, 281, 54, 259, -448, -371, 91, 170, -491, -76, 166, -285, -328, 283, -247, -223, 201, 58, 39, -303, 409, -232, 474, 276, -415, -288, 103, -290, 146], [-397, 248, -409, 128, 354, -375, 221, -380, 157, -294, -137, 73, -107, -298, 241, 195, 186, 41, 423, -422, -356, -209, -277, -240, -397, -437, 269, 81, 367, 353, 194, 239, 70, 330, -242, -9, -137, -409, 252, -287, 205, 481, -28, 119, 419, -107, -167, 372, 31, 278, 79, 226, 166, -276, 128, 360, 371, 126, -277, 231], [-227, 372, 175, -379, 461, 497, 404, -111, -196, 498, -451, 305, 273, -60, -197, -359, 81, -419, -76, 422, -235, 282, 237, -412, -404, -356, 20, 346, 177, -116, 438, -118, -251, 182, -203, 190, 326, -126, -171, 240, -116, -498, 295, 382, -424, 467, -226, 354, -60, -33, -211, 68, -71, 495, 129, -176, -11, -376, -250, 136], [135, -430, -349, -267, -492, 285, -217, -332, 262, -35, -235, 15, -224, 367, -333, 479, 177, 117, -474, 235, -275, -389, -194, -442, 40, -208, 150, 35, -224, -373, -296, 55, 329, -485, -346, -265, 117, 324, -353, 378, 136, -136, 305, 20, -309, -57, 291, -213, -336, 230, 148, 465, 367, -251, -386, -385, -152, 129, 280, -71], [343, -213, 54, -435, -113, -8, 109, 315, -228, -19, -328, 23, -272, -408, 328, 46, 80, 187, -338, -490, 122, -112, 234, 92, -222, -247, -165, 282, -255, -350, 372, -48, -312, -16, -208, -480, -51, -19, 263, -342, -306, -137, -37, -7, 160, 398, -305, -440, -35, -411, 11, -17, 105, -488, 480, -100, 417, -206, 50, -36], [-270, -253, 93, -299, -203, -217, -307, 292, -404, -20, 190, 150, -397, -372, 483, -196, 484, -300, 303, 418, 240, -24, -239, 282, 432, -240, -217, -253, 132, 442, -183, -286, -378, -184, -20, -464, -118, 80, -211, 333, -456, -456, -81, 496, 308, 393, 89, -316, -375, 4, 22, -191, -88, -231, -138, 339, 94, 471, 209, -128], [-396, -407, 293, -42, 176, -116, -330, -111, 237, -13, -258, 54, -230, -256, 494, -264, 265, -146, 168, 458, -366, -98, -361, 390, -228, 206, -459, 498, -141, -139, 179, 204, -471, -278, -382, -408, -53, -21, 302, 413, -90, 255, -215, -357, 280, 309, -259, 91, 319, -378, -120, 99, -134, 498, -228, 36, 410, 491, -66, 367], [-192, -221, 359, -466, 299, -203, -357, 69, -401, 222, -150, 192, 188, 133, 424, 54, 355, -338, -138, 65, -406, 52, 196, -405, -233, 454, 326, -213, -488, -306, -169, -410, -254, 335, -427, -51, 344, 181, -121, 111, 222, 319, 344, -72, -379, 434, 27, 375, -218, 184, 103, -428, -313, -225, 65, 180, -374, 211, -462, -440], [-239, 166, -108, 86, 248, -450, 134, 253, 325, 230, -46, 120, -439, -135, 324, -89, -116, 441, -449, -284, 45, 490, -287, -331, 181, -393, -102, 151, -368, 122, -117, -328, -75, 13, 403, -238, 438, 62, -409, 359, 80, -491, -340, 141, 143, -147, -198, -470, 463, 126, -150, 57, -408, -410, 422, 74, 474, -124, 8, 374], [-169, 27, -478, -185, 54, -116, -263, -290, -430, -416, 138, 33, -47, -46, 354, 171, -83, -271, -291, -219, 159, -489, 316, 333, -368, -385, -335, -13, -424, 117, 22, 327, 362, -109, 230, -425, -294, -471, 211, 100, 476, -210, 332, -67, -255, 102, 440, -424, -19, 193, -56, 1, 11, -137, -291, 165, 424, -377, -219, 235], [286, 220, 433, 258, -150, -269, 134, 190, 223, 152, -142, -30, -135, 49, 80, -266, 397, -67, -225, 116, -83, 20, -139, 169, -156, -379, 363, 32, 413, 144, 274, -313, 372, 495, 260, -334, 324, -463, -149, 213, 463, 59, -356, -354, 250, 228, -167, -75, -227, -480, -122, -278, -354, 452, 351, -332, -43, -277, -231, -294], [-115, 348, 344, 175, -247, 49, -131, -236, 118, 340, -243, 107, -309, 290, -132, 233, 431, 80, 109, -86, -195, -320, 339, 173, 4, -131, 246, -34, 271, -375, -477, -246, 300, -48, -430, 369, -126, -488, 217, -106, 252, -157, -195, 17, 398, -414, -143, -481, -51, 109, -460, 316, 337, -394, -272, -164, -183, 336, 28, -197]]\n",
    "    r = Solution().getMaxMatrix(m)\n",
    "    print(r)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(1,n):\n",
    "                matrix[i][j]+=matrix[i][j-1]\n",
    "        \n",
    "        s = float(\"-inf\")\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                pre = 0\n",
    "                min_pre = 0\n",
    "                min_pre_idx = 0\n",
    "                for k in range(m):\n",
    "                    if pre<min_pre:\n",
    "                        min_pre = pre\n",
    "                        min_pre_idx = k\n",
    "                    \n",
    "                    pre+=matrix[k][j]-(0 if i==0 else matrix[k][i-1])\n",
    "                    \n",
    "                    if pre-min_pre>s:\n",
    "                        s = pre-min_pre\n",
    "                        ans = [min_pre_idx,i,k,j]\n",
    "        return ans \n",
    "\n",
    "                        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        pre = [[0]*(n+1) for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pre[i][j+1] = pre[i][j] + matrix[i][j]\n",
    "        print(pre)\n",
    "        max_ = matrix[0][0]\n",
    "        ans = [0,0,0,0]\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "\n",
    "                tmp_value = 0\n",
    "                start_row = 0 \n",
    "                for k in range(m):\n",
    "                    if tmp_value >= 0:\n",
    "                        tmp_value += pre[k][j+1] - pre[k][i]\n",
    "                    else:\n",
    "                        tmp_value = pre[k][j+1] - pre[k][i]\n",
    "                        start_row = k\n",
    "                    if tmp_value > max_:\n",
    "                        ans = [start_row,i,k,j]\n",
    "                        max_ = tmp_value\n",
    "        # print(pre,max_)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        pre_s = [[0] * n for _ in range(m+1)]\n",
    "        for c in range(n):\n",
    "            for r in range(1, m+1):\n",
    "                pre_s[r][c] = pre_s[r-1][c] + matrix[r-1][c]\n",
    "        print(pre_s)\n",
    "\n",
    "        max_s = -inf\n",
    "        r1 = c1 = r2 = c2 = -1\n",
    "        for i in range(m):\n",
    "            for j in range(i, m):\n",
    "                b = [pre_s[j+1][c] - pre_s[i][c] for c in range(n)]\n",
    "                f = [-inf for _ in range(n+1)]\n",
    "                # for c in range(n):\n",
    "                #     for r in range(i, j+1):\n",
    "                #         b[c] += matrix[r][c]\n",
    "                begin = 0\n",
    "                for k, x in enumerate(b):\n",
    "                    if f[k] > 0:\n",
    "                        f[k+1] = f[k] + x\n",
    "                    else:\n",
    "                        f[k+1] = x\n",
    "                        begin = k\n",
    "                    if f[k+1] > max_s:\n",
    "                        max_s = f[k+1]\n",
    "                        r1 = i\n",
    "                        r2 = j\n",
    "                        c1 = begin\n",
    "                        c2 = k\n",
    "        return [r1, c1, r2, c2]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
